单调栈的用法

概念

从栈底到栈顶，元素单调的栈

分类

1. 递减栈，从栈底到栈顶元素递减
2. 递增站，从栈底到栈顶元素递增

用法

1. 递减栈用于找一个元素左右两边第一个比它大的
2. 递增栈用于找一个元素左右两边第一个比它小的

格式

递增栈格式

while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
                其他操作
}

mono_stack.push(i)

递减栈格式

while (!mono_stack.isEmpty() && heights[mono_stack.peek()] <= heights[i]) {
                mono_stack.pop();
                其他操作
}
mono_stack.push(i)

例题

柱状图中最大的矩形

题目

思路

最大矩形取决于两侧第一个小的柱，所以最暴力的思路就是从一个柱的左右扩散搜，时间复杂度O(n*n)，空间复杂度O(1)
那么左右扩散搜有没有必要全搜？没必要，搜到第一个比自己小的值就可以了。
因此使用递增栈。

代码

		int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];

        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        //找左侧第一个比自己小的元素，如果可以没有，则为left为-1
        for (int i = 0; i < n; ++i) {
        
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            //
            if(!mono_stack.isEmpty()){
                left[i]=mono_stack.peek();
            }else{
                left[i]=-1;
            }

            mono_stack.push(i);
        }

        mono_stack.clear();
        //找右侧第一个比自己小的元素，如果可以没有，则为right为n
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }

            if(!mono_stack.isEmpty()){
                right[i]=mono_stack.peek();
            }else{
                right[i]=n;
            }

            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;

每日温度

题目

思路

要求右边第一个比它大的，可以用递减栈。
若当前遍历到i为下标的元素甲，栈中是递减的元素，那么如果甲比栈顶的元素大，那么甲一定就是栈顶元素右侧第一个大的元素，栈顶出栈，新栈顶继续比较，直到栈顶比甲大停止，甲进栈

代码

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length];
        Deque<Integer> stack = new LinkedList<Integer>();
        //递减栈解决右边一个大的
        for (int i = 0; i < length; i++) {
            int temperature = temperatures[i];
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                //当前值下标是前面任何一个比他小的需要的
                ans[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        return ans;
    }
}