单调栈思路

栈是一种先进后出的数据结构，单调栈指的是一个栈内的数据一直保持单调递增或者单调递减，一般用于实现下一个更大元素和找字典序最小的题目。大致的模版如下：

stack<char> s;
for (int i = 0; i < str.size(); i++){
    while (!s.empty() && s.top() < str[i]){
        s.pop();
    }
    s.push(str[i]);
}

单调栈题目

316.去除重复字母

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1：
输入：s = “bcabc”
输出：”abc”

示例 2：
输入：s = “cbacdcbc”
输出：”acdb”

提示：
1 <= s.length <= 104
s 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicate-letters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

将一个字符串去重，并且要保证字典序最小。用一个整型数组来记录每个字符出现的次数，一个布尔数组来记录每个字符有没有进入到栈里。

一开始栈是空的，然后不断将符合条件字符加入进去，并且需要判断栈顶元素是否可以删除。
在栈中的字符可以跳过；不在栈中的字符就需要一直判断栈顶的字符是否可以删除，然后再把字符加入栈中。

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> num(26,0);    // 记录字符出现次数
        vector<bool> exist(26,0); // 记录字符是否在栈中
        // 统计出现次数
        for (char c : s)
            num[c - 'a']++;
        // 可以直接用string来模拟栈
        string ans = "";
        for (char c : s){
            // 如果在栈中，就跳过，并且出现次数减一
            // 如果不在栈中，就需要一直判断栈顶的字符是否可以删除，然后再把字符加入栈中
            // 可以删除的条件是 栈顶字符要比现在的字符大，并且栈顶字符后面出现的次数要大于0
            // 这样就可以保证最小字典序
            if (!exist[c - 'a']){
                while(ans.size() && ans.back() > c && num[ans.back() - 'a'] > 0){
                    exist[ans.back() - 'a'] = false;
                    ans.pop_back();
                }
                ans.push_back(c);
                exist[c - 'a'] = true;
            }
            num[c - 'a']--;
        }
        return ans;
    }
};

402.移掉k位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 1 ：
输入：num = “1432219”, k = 3
输出：”1219”
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

示例 2 ：
输入：num = “10200”, k = 1
输出：”200”
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 ：
输入：num = “10”, k = 2
输出：”0”
解释：从原数字移除所有的数字，剩余为空就是 0 。

提示：
1 <= k <= num.length <= 105
num 仅由若干位数字（0 - 9）组成
除了 0 本身之外，num 不含任何前导零

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-k-digits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

将一个字符串去掉k个字符并使剩下的数字最小。

class Solution {
public:
    string removeKdigits(string num, int k) {
        string ans;
        for (int i = 0; i < num.size(); i++){
            // 保证前面的字符尽可能小
            while (!ans.empty() && k > 0 && ans.back() > num[i]){
                ans.pop_back();
                k--;
            }
            // 如果剩下的字符数等于k，那么需要都删掉
            if (num.size() - i > k)
                ans.push_back(num[i]);
            else
                k--;
        }
        // 去除前导零
        int i = 0;
        while(ans[i] == '0') i++;
        ans = ans.substr(i);
        // 需要判断是不是空字符
        return ans == "" ? "0" : ans;
    }
};

496.下一个更大元素

给你两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

提示：
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数互不相同
nums1 中的所有整数同样出现在 nums2 中

进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-greater-element-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这题其实相当于在数组2中找到下一个更大元素。
暴力法：

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<int> res(n, -1);
        bool isNum = false;
        for (int i = 0; i < n; i++){
            int j = 0;
            while (j < m){
                if (nums2[j++] == nums1[i]){
                    isNum = true;
                    break;
                }
            }
            while (j < m){
                if (nums2[j++] > nums1[i]){
                    res[i] = nums2[j-1];
                    break;
                }
            }
        }
        return res;
    }
};

也可以用单调栈实现O(n+m)复杂度，先求出第二个数组中每个元素的下一个更大元素储存到哈希表中。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<int> res(n, -1);
        unordered_map<int, int> map;
        stack<int> s;

        for (int i = 0; i < m; i++){
            while (!s.empty() && nums2[i] > s.top()){
                map[s.top()] = nums2[i];
                s.pop();
            }
            s.push(nums2[i]);
        }
        for (int i = 0; i < n; i++){
            if (map.count(nums1[i]))
                res[i] = map[nums1[i]];
        }
        return res;
    }
};

503.下一个更大元素 II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
注意: 输入数组的长度不会超过 10000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-greater-element-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

对一个循环数组求下一个更大元素，可以循环两次数组，并且取模来模拟循环数组。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        stack<int> s;
        vector<int> res(n, -1);
        for (int i = 0; i < n * 2 - 1; i++){
            while (!s.empty() && nums[s.top()] < nums[i % n]){
                res[s.top()] = nums[i % n];
                s.pop();
            }
            s.push(i % n);
        }
        return res;
    }
};

2030.含特定字母的最小序列

给你一个字符串 s ，一个整数 k ，一个字母 letter 以及另一个整数 repetition 。
返回 s 中长度为 k 且字典序最小的子序列，该子序列同时应满足字母 letter 出现至少 repetition 次。生成的测试用例满足 letter 在 s 中出现至少 repetition 次。
子序列是由原字符串删除一些（或不删除）字符且不改变剩余字符顺序得到的剩余字符串。
字符串 a 字典序比字符串 b 小的定义为：在 a 和 b 出现不同字符的第一个位置上，字符串 a 的字符在字母表中的顺序早于字符串 b 的字符。

示例 1：
输入：s = “leet”, k = 3, letter = “e”, repetition = 1
输出：”eet”
解释：存在 4 个长度为 3 ，且满足字母 ‘e’ 出现至少 1 次的子序列：

“lee”（”leet”）
“let”（”leet”）
“let”（”leet”）
“eet”（”leet”）
其中字典序最小的子序列是 “eet” 。

示例 2：
输入：s = “leetcode”, k = 4, letter = “e”, repetition = 2
输出：”ecde”
解释：”ecde” 是长度为 4 且满足字母 “e” 出现至少 2 次的字典序最小的子序列。

示例 3：
输入：s = “bb”, k = 2, letter = “b”, repetition = 2
输出：”bb”
解释：”bb” 是唯一一个长度为 2 且满足字母 “b” 出现至少 2 次的子序列。

提示：
1 <= repetition <= k <= s.length <= 5 * 104
s 由小写英文字母组成
letter 是一个小写英文字母，在 s 中至少出现 repetition 次

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

第261场周赛的最后一题，题目的要求比较多。首先要求最小字典序，那么就要用到单调栈了。然后字符长度要是k，并且有一个字母必须要出现一定次数。

为了实现一个字母必须出现一定次书，我们首先要统计它的总共出现次数，求出可以删除的数量。然后在使用单调栈道过程中需要加上这个字母的判断。求完最小字典序之后，还需要将字符压缩到k的长度。因为已经是最小字典序了，所以我们要从后面删除字符，并且统计删除了指定字符的次数。最后在字符的后面补上特定字符。

class Solution {
public:
    string smallestSubsequence(string s, int k, char letter, int repetition) {
        string ans;

        // 统计该字符出现次数，和需要删除字符的数量
        int cnt = 0, toDel = s.size() - k;
        for (char c : s){
            if (c == letter)
                cnt++;
        }
        cnt -= repetition;

        // 求最小字典序
        for (char c : s){
            while (!ans.empty() && toDel && c < ans.back()){
                if (ans.back() == letter){
                    if (cnt)
                        cnt--;
                    else
                        break;
                }
                toDel--;
                ans.pop_back();
            }
            ans.push_back(c);
        }
        
        // 删除多余的字符，并且统计删除的特定字符数量
        while (ans.size() > k){
            if (ans.back() == letter) 
                cnt--;
            ans.pop_back();
        }

        // 在字符串的最后补上该字符
        for (int i = k - 1; cnt < 0; i--){
            if (ans[i] != letter){
                ans[i] = letter;
                cnt++;
            }
        }
        return ans;
    }
};

参考资料

https://leetcode-cn.com/problems/remove-k-digits/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-5/

https://github.com/labuladong/fucking-algorithm/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%B3%BB%E5%88%97/%E5%8D%95%E8%B0%83%E6%A0%88.md

https://leetcode-cn.com/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/solution/lt-mo-ni-by-landen-zql8/

我的「精神家园」

数据结构与算法-单调栈