单调栈

性质

• 元素满足单调性的堆栈
• 元素加入栈前，会在栈顶端把破坏栈单调性的元素都删除

使用

• 通常应用在一维数组，和前后元素大小有关系
• 若求右边变大数，则维护递减栈，反之维护递增栈

典型题

leetcode 739 每日温度

• 每个元素最多只有一次入栈和出栈的机会，时间复杂度为O(n)，暴力法为O(n2)
• 维护单调递减栈，只要发现上升元素，则将小元素出栈，同时计算小元素和当前元素的天数

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        int[] res = new int[len];
        Arrays.fill(res, 0);
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int topIdx = stack.pop();
                res[topIdx] = i - topIdx;
            }
            stack.push(i);
        }
        return res;
    }
}

leetcode 503 下一个更大的元素

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = 0; i < 2 * len; i++) {
            int idx = i % len;
            while (!stack.isEmpty() && nums[idx] > nums[stack.peek()]) {
                int index = stack.pop();
                res[index] = nums[idx];
            }
            stack.push(idx);
        }
        return res;
    }
}

leetcode 84 柱状图中最大的矩形

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] array = new int[len + 1];
        System.arraycopy(heights, 0, array, 0, len);
        array[len] = 0;
        int res = 0;
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = 0; i < (len + 1); i++) {
            while(!stack.isEmpty() && array[i] < array[stack.peek()]) {
                int idx = stack.pop();
                int wid = stack.isEmpty() ? -1 : stack.peek();
                int area = array[idx] * (i - wid - 1);
                res = Math.max(res, area);
            }
            stack.push(i);
        }
        return res;
    }
}