> For the complete documentation index, see [llms.txt](https://mabuxi.gitbook.io/mabuxi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mabuxi.gitbook.io/mabuxi/leetcode-summary/data-structure/dan-tiao-zhan-dan-tiao-dui-lie.md).

# 单调栈/单调队列

## 别人做的总结

[LeetCode Monotone Stack Summary 单调栈小结](http://www.cnblogs.com/grandyang/p/8887985.html)

## 经典题目

[*84 Largest Rectangle in Histogram*](https://leetcode.com/problems/largest-rectangle-in-histogram/description/)

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. 

```java
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*](https://leetcode.com/problems/sliding-window-maximum/description/)

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

{% tabs %}
{% tab title="General Max/Min" %}

```java
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;
}
```

{% endtab %}

{% tab title="Sliding Window Maximum" %}

```java
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> destack = new LinkedList<>();
        if (nums == null || nums.length == 0) return nums;
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            while (!destack.isEmpty() && nums[destack.peekLast()] < cur) {
                destack.pollLast();
            }
            destack.offerLast(i);
            if (i >= k - 1) {
                // [i - k + 1 , i]
                if (destack.peekFirst() < i - k + 1) {
                    destack.pollFirst();
                }
                res[i - k + 1] = nums[destack.peekFirst()];
            }
        }
        return res;
    }
}
```

{% endtab %}
{% endtabs %}