栈

基本概念

栈是一种很常用，很基础的数据结构。用于存储元素，支持元素的加入和取出。最大的特点就是元素的写入和写入顺序为先进后出。举一个现实的例子，想象一叠垒起来的盘子，先放入的盘子在下面，后放入的在上面。当你要拿取盘子的时候，想拿下面的盘子要先把上面的盘子移开。

栈应用非常广泛，函数调用靠栈来维护调用顺序，对于匹配的验证，对于元素和其左右元素大小关系的寻找等场景都会用到栈。

基础实现

java中两种方式使用栈，stack和deque（双端队列）。推荐使用双端队列来实现。

Deque<Integer> stack = new LinkedList<>();
stack.push(1);
stack.pop();
stack.peek();
stack.isEmpty();

实现细节

栈的最常见的应用，对括号的匹配lc20

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(c=='{' || c=='(' || c=='['){
                stack.push(c);
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                char left = stack.pop();
                if(c=='}' && left!='{'){
                    return false;
                }
                if(c==']' && left != '['){
                    return false;
                }
                if(c==')' && left != '('){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

进阶情况

单调栈的应用，所谓单调栈，就是栈内元素是单调增或者单调减的。这样的好处是对于每个元素，我都能找到其左右第一个大于/小于它的元素。这也是单调栈的核心作用。

单调增的栈，可以找到每个元素右边第一个小于它的元素

单调减的栈，可以找到每个元素右边第一个大于它的元素

具体说明，以单调减栈为例，对于每个新的元素，如果发现当前栈顶比它大，则栈顶要出栈，直到栈顶小于等于它，它入栈。此时它下面的元素就是它左边第一个大于等于它的元素。还是拿这个元素看，当它出栈的时候，遍历到的当前元素就是右边比它大的元素。

列几个经典问题：

lc42 接雨水

这个题利用单调栈的性质，每次找当前元素前面比它小的元素，这样就形成了一个水坑，能够接到雨水。找比它小的元素说明这个栈是一个单调减的栈，那仍旧在栈顶的元素一定比弹出的元素大，因此能够储藏水的高度就是当前栈顶以及当前出栈元素中小的那个和出栈元素的高度差。宽度就是当前元素和出栈元素的间隔。

class Solution {
    public int trap(int[] height) {
        Deque<Integer> stack = new LinkedList<>();
        int total = 0;
        for(int i=0;i<height.length;i++){
            while(!stack.isEmpty() && height[i]>height[stack.peek()]){
                int pop = stack.pop();
                if(!stack.isEmpty()){
                    total += (Math.min(height[stack.peek()],height[i])-height[pop])*(i-stack.peek()-1);
                }
            }
            stack.push(i);
        }
        return total;
    }
}

lc84 柱状图的最大矩形面积

这里也是典型的单调栈应用，是一个单调增的栈，对于每个新元素，如果栈顶比它大，说明可以以它的高度组成长方形，栈顶出栈，更新结果。如果栈顶比它小，则无法更新，直接入栈。

这里另外一个重要技巧是守卫元素的加入。为了防止所有元素本来就是单调的，给元素的头尾各加入一个为0的守卫元素。这样就不会出现所有元素全部进栈，没有出栈的情况了。

class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new LinkedList<>();
        int[] newHeights = new int[heights.length + 2];
        for (int i = 1; i < newHeights.length - 1; i++) {
            newHeights[i] = heights[i - 1];
        }
        int res = 0;
        for (int i = 0; i < newHeights.length; i++) {
            while (!stack.isEmpty() && newHeights[stack.peek()] > newHeights[i]) {
                int current = stack.pop();
                res = Math.max(res, (i-stack.peek()-1)*newHeights[current]);
            }
            stack.push(i);
        }
        return res;
    }
}

lc739 每日温度

这就是最本质的单调栈应用，没有变体，题目要求就是找到每个元素右边第一个比它大的元素。

那直接用单调减的栈，如果当前元素大于栈顶，则对于栈顶的元素就是找到了，直接出栈，更新就好。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> st = new LinkedList<>();
        int[] res = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            while (!st.isEmpty() && temperatures[st.peek()] < temperatures[i]) {
                int current = st.pop();
                res[current] = i - current;
            }
            st.push(i);
        }
        return res;
    }
}

总结：单调栈根据具体要求进行选择，模拟一下过程，看到底用增还是减。不要死记硬背，反而效果不好。