前言
算法中的单调栈应用十分的广泛；单调栈简单的来说就是栈内元素单调递增或者单调递减的栈，同时单调栈还可以不断的维护一组某种或多种规律的数据，利用这一性质可以解决许多算法问题。本文主要讲解单调栈的算法用法，需对单调栈具有一定的了解。
问题描述
问题一
给你一个字符串 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，故此将其长度缩减至k while(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; } }; |
结语
本文主要分享了两道力扣经典的单调栈算法题，其共同的性质都是求最小字典序的子序列，且其余性质均满足单调栈维护；需要对单调栈有了解的朋友进行阅读，了解其单调栈的模板与维护方法。
