# 单调栈/单调队列

## 别人做的总结

[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 %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mabuxi.gitbook.io/mabuxi/leetcode-summary/data-structure/dan-tiao-zhan-dan-tiao-dui-lie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.