前言
算法中的單調(diào)棧應(yīng)用十分的廣泛；單調(diào)棧簡(jiǎn)單的來(lái)說(shuō)就是棧內(nèi)元素單調(diào)遞增或者單調(diào)遞減的棧，同時(shí)單調(diào)棧還可以不斷的維護(hù)一組某種或多種規(guī)律的數(shù)據(jù)，利用這一性質(zhì)可以解決許多算法問(wèn)題。本文主要講解單調(diào)棧的算法用法，需對(duì)單調(diào)棧具有一定的了解。
問(wèn)題描述
問(wèn)題一
給你一個(gè)字符串 s ，一個(gè)整數(shù) k ，一個(gè)字母 letter 以及另一個(gè)整數(shù) repetition 。返回 s 中長(zhǎng)度為 k 且 字典序最小 的子序列，該子序列同時(shí)應(yīng)滿足字母 letter 出現(xiàn) 至少 repetition 次。生成的測(cè)試用例滿足 letter 在 s 中出現(xiàn)至少 repetition 次。
子序列 是由原字符串刪除一些（或不刪除）字符且不改變剩余字符順序得到的剩余字符串。
字符串 a 字典序比字符串 b 小的定義為：在 a 和 b 出現(xiàn)不同字符的第一個(gè)位置上，字符串 a 的字符在字母表中的順序早于字符串 b 的字符。
樣例：
輸入：s = "leetcode", k = 4, letter = "e", repetition= 2
輸出："ecde"
解釋："ecde" 是長(zhǎng)度為 4 且滿足字母 "e" 出現(xiàn)至少 2 次的字典序最小的子序列。
題目來(lái)源 力扣：5893. 含特定字母的最小子序列
https://leetcode-cn.com/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/
題目分析
題意：此題主要描述的是需要維護(hù)一個(gè)長(zhǎng)度為k的字典序最小且至少出現(xiàn)repetition 次letter字母的s的子序列，關(guān)鍵詞就是維護(hù)一個(gè)長(zhǎng)度為k的字典序最小的子序列，子序列中包含至少repetition 個(gè)letter字母；此題的正好符合單調(diào)棧的性質(zhì)，利用單調(diào)棧來(lái)維護(hù)以上性質(zhì)！
維護(hù)三種性質(zhì)：
性質(zhì)1：維護(hù)字典序單增的字符串。(滿足題意中的字典序最小這一性質(zhì))
性質(zhì)2：維護(hù)長(zhǎng)度為k的字符串。(滿足題中長(zhǎng)度為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ù)長(zhǎng)度為不低于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ù)的字符串為長(zhǎng)度不低于k的字符串，其長(zhǎng)度可能超過(guò)k，故此將其長(zhǎng)度縮減至k
while(ans.size() > k) {
if (ans.back() == letter) p --;
ans.pop_back();
}
// 在縮減至k的操作過(guò)程中，可能將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;
}
};
問(wèn)題二
返回 s 字典序最小的子序列，該子序列包含 s 的所有不同字符，且只包含一次。
樣例
輸入：s ="cbacdcbc"
輸出："acdb"
題目來(lái)源 力扣：1081. 不同字符的最小子序列
https://leetcode-cn.com/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;
}
};
結(jié)語(yǔ)
稿件來(lái)源：深度學(xué)習(xí)與文旅應(yīng)用實(shí)驗(yàn)室（DLETA）
