单调栈的经典例题

前言算法中的单调栈应用十分的广泛；单调栈简单的来说就是栈内元素单调递增或者单调递减的栈，同时单调栈还可以不断的维护一组某种或多种规律的数据，利用这一性质可以解决许多算法问题。本文主要讲解单调栈的算法用法，需对单调栈具有一定的了解。问题描述问题一给你一个字符串 s ，一个整数 k ，一个字母 letter 以及另一个整数 repetition 。返回 s 中长度为 k 且 字典序最小 的子序列，该子序列同时应满足字母 letter 出现 至少 repetition 次。生成的测试用例满足 letter 在 s 中出现至少 repetition 次。子序列 是由原字符串删除一些（或不删除）字符且不改变剩余字符顺序得到的剩余字符串。字符串 a 字典序比字符串 b 小的定义为：在 a 和 b 出现不同字符的第一个位置上，字符串 a 的字符在字母表中的顺序早于字符串 b 的字符。样例：输入：s = "leetcode", k = 4, letter = "e", repetition= 2输出："ecde"解释："ecde" 是长度为 4 且满足字母 "e" 出现至少 2 次的字典序最小的子序列。题目来源 力扣：5893. 含特定字母的最小子序列https://leetcode-cn.com/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/题目分析题意：此题主要描述的是需要维护一个长度为k的字典序最小且至少出现repetition 次letter字母的s的子序列，关键词就是维护一个长度为k的字典序最小的子序列，子序列中包含至少repetition 个letter字母；此题的正好符合单调栈的性质，利用单调栈来维护以上性质！维护三种性质：性质1：维护字典序单增的字符串。(满足题意中的字典序最小这一性质)性质2：维护长度为k的字符串。(满足题中长度为k的字符串这一性质)性质3：维护子序列中包含至少repetition 个letter字母。(同理满足题意性质)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]统计在i的右侧还有多少个letter，便于后续维护}string ans;int p = 0; // p用于记录当前维护字符串中的letter数量// 单调栈模板for (int i = 0; i < n; i  ++){char c = s[i];// 维护字典序单调增的字符串while(!ans.empty()  && c < ans.back()){// 维护长度为不低于k的字符串if (ans.size() - 1  + n - i < k) break;if (ans.back() ==  letter){// 维护子序列中包含至少repetition  个letter字母if (p - 1 +  cnt[i] < repetition) break;p --;}ans.pop_back();}if (c == letter) p ++,  cnt[i] --;ans.push_back(c);}// 因为最终维护的字符串为长度不低于k的字符串，其长度可能超过k，故此将其长度缩减至kwhile(ans.size() > k) {if (ans.back() ==  letter) p --;ans.pop_back();}// 在缩减至k的操作过程中，可能将letter减去，导致字符串中的letter个数少于repetition// 所以如果letter个数少于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://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/题目分析此题与上一题类似，求一个最小字典序的子序列，且子序列的必须包含s中所有不同的字符只包含一次。维护二种性质：性质一：维护一个字典序最小的子序列。性质二：维护包含所有不同字符且只包含一次的子序列。class Solution {public:// cnt记录在s中从i向右中还存在的多少个对应字符int cnt[28];// snt记录字符在维护的字符串中是否存在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';// 维护最小字典序的子序列while(!t.empty()  && t.back() > c) {int x = t.back() -  'a';// 维护包含所有不同字符且只包含一次的子序列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;}};结语稿件来源：深度学习与文旅应用实验室（DLETA）