单调栈/单调队列

别人做的总结

LeetCode Monotone Stack Summary 单调栈小结

经典题目

84 Largest Rectangle in Histogram

We need to maintain a monotonically increasing stack, so that we can easily calculate the largest rectangle area whenever we meet a new bar i. Each time we meet a new bar i, if the height of the new bar heights[i] is larger than the top element of the stack heights[stack.peekLast()], we just push it into the stack and finish this round. Otherwise, we pop out the top element of the stack height = heights[stack.pollLast()], and we calculate the area of the rectangle centered at the popped element. So the height is the popped element's height, and the left boundary would be stack.peekLast() + 1, the right boundary would be i - 1. Thus, the area center at the popped element would be height * (i - 1 - stack.peekLast() - 1 + 1), which would be the largest rectangle centered at the popped element.

public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new LinkedList<>();
    int max = 0;
    for (int i = 0; i <= heights.length; i++) {
        // To pop out all the elements in the stack at last, so we explicitly add a bar of height 0.
        int cur = i == heights.length ? 0 : heights[i];
        while (!stack.isEmpty() && heights[stack.peekLast()] >= cur) {
            int height = heights[stack.pollLast()];
            // Dertermine the left boundary of the largest rectangle with height heights[i]
            int left = stack.isEmpty() ? 0 : stack.peekLast() + 1;
            // Dertermine the right boundary of the largest rectangle with height of the poped element
            max = Math.max(max, height * (i - 1 - left + 1));
        }
        stack.offerLast(i);
    }
    return max;
}

239 Sliding Window Maximum

这里也是维护一个单调栈（max的话，递减栈；min的话，递增栈）

General Max/Min

public static int[] compute(int[] array, int window, boolean maximize) {
    int[] result = new int[array.length - window + 1];
    Deque<Integer> deque = new ArrayDeque<>();
    for (int i = 0; i < array.length; i++) { // Range end index (inclusive)
        int val = array[i];
        while (!deque.isEmpty() && (!maximize && val < deque.getLast() || maximize && val > deque.getLast()))
            deque.removeLast();
        deque.addLast(val);
        
        int j = i + 1 - window; // Range start index, does not overflow
        if (j >= 0) {
            result[j] = deque.getFirst();
            if (array[j] == result[j])
                deque.removeFirst();
        }
    }
    return result;
}

Sliding Window Maximum