|
算法中的單調(diào)棧應(yīng)用十分的廣泛；單調(diào)棧簡單的來說就是棧內(nèi)元素單調(diào)遞增或者單調(diào)遞減的棧，同時(shí)單調(diào)棧還可以不斷的維護(hù)一組某種或多種規(guī)律的數(shù)據(jù)，利用這一性質(zhì)可以解決許多算法問題。本文主要講解單調(diào)棧的算法用法，需對(duì)單調(diào)棧具有一定的了解。 問題一給你一個(gè)字符串 s ，一個(gè)整數(shù) k ，一個(gè)字母 letter 以及另一個(gè)整數(shù) repetition 。返回 s 中長度為 k 且 字典序最小 的子序列，該子序列同時(shí)應(yīng)滿足字母 letter 出現(xiàn) 至少 repetition 次。生成的測試用例滿足 letter 在 s 中出現(xiàn)至少 repetition 次。 子序列 是由原字符串刪除一些（或不刪除）字符且不改變剩余字符順序得到的剩余字符串。 字符串 a 字典序比字符串 b 小的定義為：在 a 和 b 出現(xiàn)不同字符的第一個(gè)位置上，字符串 a 的字符在字母表中的順序早于字符串 b 的字符。 樣例： 輸入：s = "leetcode", k = 4, letter = "e", repetition= 2 輸出："ecde" 解釋："ecde" 是長度為 4 且滿足字母 "e" 出現(xiàn)至少 2 次的字典序最小的子序列。 題目來源 力扣：5893. 含特定字母的最小子序列 https:///problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/ 題目分析題意：此題主要描述的是需要維護(hù)一個(gè)長度為k的字典序最小且至少出現(xiàn)repetition 次letter字母的s的子序列，關(guān)鍵詞就是維護(hù)一個(gè)長度為k的字典序最小的子序列，子序列中包含至少repetition 個(gè)letter字母；此題的正好符合單調(diào)棧的性質(zhì)，利用單調(diào)棧來維護(hù)以上性質(zhì)！ 維護(hù)三種性質(zhì)： 性質(zhì)1：維護(hù)字典序單增的字符串。(滿足題意中的字典序最小這一性質(zhì)) 性質(zhì)2：維護(hù)長度為k的字符串。(滿足題中長度為k的字符串這一性質(zhì)) 性質(zhì)3：維護(hù)子序列中包含至少repetition 個(gè)letter字母。(同理滿足題意性質(zhì)) const int N = 50010; class Solution { public: int cnt[N]; string smallestSubsequence(string s, int k, char letter, int repetition) { int n = s.size(); for (int i = n-1; i >= 0; i --){ if (s[i] == letter) cnt[i] = cnt[i + 1] + 1; else cnt[i] = cnt[i+1]; //cnt[i]統(tǒng)計(jì)在i的右側(cè)還有多少個(gè)letter，便于后續(xù)維護(hù) } string ans; int p = 0; // p用于記錄當(dāng)前維護(hù)字符串中的letter數(shù)量 // 單調(diào)棧模板 for (int i = 0; i < n; i ++){ char c = s[i]; // 維護(hù)字典序單調(diào)增的字符串 while(!ans.empty() && c < ans.back()){ // 維護(hù)長度為不低于k的字符串 if (ans.size() - 1 + n - i < k) break; if (ans.back() == letter){ // 維護(hù)子序列中包含至少repetition 個(gè)letter字母 if (p - 1 + cnt[i] < repetition) break; p --; } ans.pop_back(); } if (c == letter) p ++, cnt[i] --; ans.push_back(c); } // 因?yàn)樽罱K維護(hù)的字符串為長度不低于k的字符串，其長度可能超過k，故此將其長度縮減至k while(ans.size() > k) { if (ans.back() == letter) p --; ans.pop_back(); } // 在縮減至k的操作過程中，可能將letter減去，導(dǎo)致字符串中的letter個(gè)數(shù)少于repetition // 所以如果letter個(gè)數(shù)少于repetition需要將字符串的末尾值換位letter即可滿足 for (int i = ans.size() - 1; i >= 0; i --){ if (p < repetition && ans[i] != letter) { ans[i] = letter; p ++; } } return ans; } }; |
問題二返回 s 字典序最小的子序列，該子序列包含 s 的所有不同字符，且只包含一次。 樣例 輸入：s ="cbacdcbc" 輸出："acdb" 題目來源 力扣：1081. 不同字符的最小子序列 https:///problems/smallest-subsequence-of-distinct-characters/ 題目分析此題與上一題類似，求一個(gè)最小字典序的子序列，且子序列的必須包含s中所有不同的字符只包含一次。 維護(hù)二種性質(zhì)： 性質(zhì)一：維護(hù)一個(gè)字典序最小的子序列。 性質(zhì)二：維護(hù)包含所有不同字符且只包含一次的子序列。 class Solution { public: // cnt記錄在s中從i向右中還存在的多少個(gè)對(duì)應(yīng)字符 int cnt[28]; // snt記錄字符在維護(hù)的字符串中是否存在 bool snt[28]; string smallestSubsequence(string s) { string t; int n = s.size(), k = 0; for (int i = n-1; i >= 0; i --){ int x = s[i] - 'a'; if (cnt[x] == 0) k ++; cnt[x] ++; } for (int i = 0; i < n; i ++){ char c = s[i]; int u = c - 'a'; // 維護(hù)最小字典序的子序列 while(!t.empty() && t.back() > c) { int x = t.back() - 'a'; // 維護(hù)包含所有不同字符且只包含一次的子序列 if (cnt[x] <= 0 || snt[u]) break; t.pop_back(); snt[x] = false; } if (!snt[u]) t.push_back(c); snt[u] = true, cnt[u] --; } return t; } }; |
稿件來源：深度學(xué)習(xí)與文旅應(yīng)用實(shí)驗(yàn)室（DLETA） |
