单调栈详解

最近几天LeetCode高强度推送单调栈的题目，以往对这个数据结构的认识都只是停留在肤浅的表层上，看了这些题目后发现这个看似简单的栈结构其实用法很多，也很灵活，于是单独开一篇文章记录学习。

单调栈介绍

顾名思义，单调栈是满足一定单调性的栈结构。现在我们通过模拟实现一个单调递减栈来了解它具体的结构。

有一组数[10,3,7,4,12]。从左到右依次入栈。当且仅当栈为空或入栈元素值小于栈顶元素值时入栈；否则将所有比入栈元素小的元素全部出栈，再进行入栈操作，以确保栈的单调性不被破坏。

• 10入栈时，栈为空，直接入栈，栈内元素为10。
• 3入栈时，栈顶元素10比3大，则入栈，栈内元素为10，3。
• 7入栈时，栈顶元素3比7小，则栈顶元素出栈，此时栈顶元素为10，比7大，则7入栈，栈内元素为10，7。
• 4入栈时，栈顶元素7比4大，则入栈，栈内元素为10，7，4。
• 12入栈时，栈顶元素4比12小，4出栈，此时栈顶元素为7，仍比12小，栈顶元素7继续出栈，此时栈顶元素为10，仍比12小，10出栈，此时栈为空，12入栈，栈内元素为12。

单调递增的栈反之即可。了解了单调栈的概念，接下来就该撸题了。

单调栈例题

LeetCode-402：移掉K位数字

传送门

思路

题目要计算一个整数去掉k个数位后的最小新整数。最直接的思路就是枚举每一种取法然后维护最小值，但这么做的复杂度显然是指数级，不能这么莽。

考虑O(n)的方法：从左到右遍历num，对每一位数字决定它是否保留，这个操作执行k次即可。那么以什么依据来判断当前数字是该留还是该舍呢？

假设有两个数字，123a456与123b456，怎么去判断它们谁大谁小呢？显然，a>b时前者大于后者，反之亦然。即，判断两个数大小关系的依据是两者第一个不同的数位大小关系。

根据上面的思路，我们只需要在枚举到每一位的时候去维护一个局部单调递增栈作为答案就好了。为什么是“局部”递增栈呢？因为题目要求我们要去掉k位数位，单调栈在不满足入栈条件的情况下会一直弹出栈内元素直到满足入栈条件，我们显然不能让它把答案全弹出去，所以当不能再弹的时候(即(n-k)-ans.size()>=n-i时)就继续去枚举下一位数位。

代码

class Solution {
public:
    string removeKdigits(string num, int k) {
        int n = num.size();
        string ans = "";
        if(n == k) return "0";
        if(k == 0) return num;
        
        for(int i = 0; i < n; i++) {
            while(ans.size() != 0 && ans[ans.size()-1] > num[i] && (n - k) - ans.size() < n - i) {
                ans.erase(ans.size() - 1);
            }
            if((n - k) != ans.size()) {
                ans += num[i];
            }
        }
        // 去掉前导0
        while(ans[0] == '0' && ans != "0") ans.erase(0,1);
        
        return ans;
    }
};

LeetCode-316：去除重复字母

传送门

思路

题目要求的是一个给定字符串再去除所有重复字母后字典序最小的子序列。