# 栈， 单调栈

## 单调栈例题

有N个人，顺次排列，他们的身高分别为H\[i]，每个人向自己后方看，他能看到的人是在他后面离他最近的且比他高的人。请依次输出每个人能看到的人的编号Next\[i]，如果他后面不存在比他高的人，则输出-1。

### 想找 "从当前元素向某一方向的第一个 (大于 / 小于) 自己的元素"，就要靠单调栈来维护单调性，对应的是 (递减 / 递增)。

```java
public class Main {

    public static int[] getHeight(int[] heights){
        int n = heights.length;
        int[] arr = new int[n];

        // Stack stores index of people
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n; i++){
            while(!stack.isEmpty() && heights[stack.peek()] <= heights[i]){
                arr[stack.pop()] = i;
            }
            stack.push(i);
        }

        while(!stack.isEmpty()){
            arr[stack.pop()] = -1;
        }

        return arr;
    }

    public static void main(String[] args){
        int[] heights1 = {3,2,5,6,1,2};
        int[] heights2 = {1,2,3,4,5,6};
        int[] heights3 = {6,5,4,3,2,1};
        int[] heights4 = {6,1,3,4,2,5};

        int[] arr = getHeight(heights4);
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + "  ");
        }
    }
}
```

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

### 顺着上一题的思路，这题比较暴力的解法可以分为三步：

* **从左向右扫，寻找对于每个元素，往右能看到的最远距离；**
* **从右向左扫，寻找对于每个元素，往左能看到的远距离；**
* **把两个 arr\[] 的结果综合起来，就是从每个位置出发能构造的最大 rectangle.**

速度非常慢，只超过了 1.27% ，因为常数项更大。虽然时间复杂度是 O(n)，但是用了 three-pass 才搞定。如果说这种解法有什么优点，就是比较好理解。。是单调栈非常简单直接的应用方式，不加任何 trick.

```java
public class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] right = findToRight(heights);
        int[] left = findToLeft(heights);

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

        return max;
    }

    private int[] findToRight(int[] heights){
        int[] right = new int[heights.length];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < heights.length; i++){
            while(!stack.isEmpty() && heights[stack.peek()] > heights[i]){
                right[stack.pop()] = i - 1;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int index = stack.pop();
            right[index] = heights.length - 1;
        }
        return right;
    }

    private int[] findToLeft(int[] heights){
        int[] left = new int[heights.length];
        Stack<Integer> stack = new Stack<>();
        for(int i = heights.length - 1; i >= 0; i--){
            while(!stack.isEmpty() && heights[stack.peek()] > heights[i]){
                left[stack.pop()] = i + 1;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int index = stack.pop();
            left[index] = 0;
        }
        return left;
    }
}
```

## [Increasing Triplet Subsequence](https://leetcode.com/problems/increasing-triplet-subsequence/)

用 LIS 的角度理解的话这题就是无脑套模板。。

不过题目要求 O(n) 时间 O(1) 空间，就得另外动动脑筋了。

```java
public class Solution {
    public boolean increasingTriplet(int[] nums) {
        if(nums == null || nums.length < 3) return false;
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int index = 0;
        for(int i = 1; i < n; i++){
            int pos = binarySearch(dp, 0, index, nums[i]);
            if(pos > index){
                dp[pos] = nums[i];
                index = pos;
                if(index + 1 >= 3) return true;
            }
            dp[pos] = Math.min(dp[pos], nums[i]);
        }
        return false;
    }

    private int binarySearch(int[] nums, int start, int end, int target){
        int left = start;
        int right = end;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid;
            } else {
                right = mid;
            }
        }

        if(target <= nums[left]) return left;
        if(target > nums[right]) return right + 1;

        return right;
    }
}
```

通过观察这题的具体性质，我们发现在这里我们所谓的 "单调栈" 长度其实是固定的，就是3，等于3了直接返回就行。

因为 3 非常小，我们只需要存两个值，分别代表着单调栈的第一个和第二个位置；当我们碰到第三个位置的情况，就可以返回 true 了。

### 这个解法的思想也可以推广到任意 k ，k比较小或者为常数的情况，毕竟对于常数 k ，O(k) = O(1).

```java
public class Solution {
    public boolean increasingTriplet(int[] nums) {
        if(nums == null || nums.length < 3) return false;
        int n = nums.length;

        int num1 = Integer.MAX_VALUE;
        int num2 = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            if(nums[i] <= num1){
                num1 = nums[i];
            } else if(nums[i] <= num2){
                num2 = nums[i];
            } else {
                return true;
            }
        }

        return false;
    }
}
```

## [Russian Doll Envelopes](https://leetcode.com/problems/russian-doll-envelopes/)

\[\[2,100],\[3,200],\[4,300],\[5,500],\[5,400],\[5,250],\[6,370],\[6,360],\[7,380]]

这题试着用 LIS 的写法思路写了一下，然而卡在了这个 test case 上。

* **因为这题，元素之间不存在绝对的大小，不能直接用两个 tuple 去比较，进行 binary search.**
* **两个 tuple \[4,300] 和 \[5,250] 之间，按理可以说 \[4, 300] 更小，但是有可能最优解是由 \[5,250] 选出来的。**

### 正解的流程：

* **按 \[w, h] 中的 w 升序排序；**
* **如果 w 相等，则按照 h 的降序排序(重要！！！)**
* **后面的就和一维 LIS 一样，只考虑 h 的维度做 LIS 就行了。**

### 难点在于，为什么这么做是正确的？

* **不难看出对于同一个 w 的楼层，我们不能按 h 升序排列，因为会延长自身，导致在同一个 w 上多次套用。**
* **因此对于同一 w 的情况， 要按照 h 降序排列**
* **这样当我们看到一个更大的 h 时，我们可以确定，这一定是一个新的 w，而且根据原来排序的单调性，一定是一个比单调栈内元素都大的新 w，可以套上。**
* **同时对于单调栈中的任意 h，如果 binary search 之后的位置 pos 位于中间，它一定可以套在 pos 之前的所有信封上。**

速度超过 87.50%，还不错。

```java
public class Solution {
    private class MyComparator implements Comparator<int[]>{
        public int compare(int[] a, int[] b){
            if(a[0] != b[0]) return (a[0] < b[0]) ? -1: 1;
            else return (a[1] < b[1]) ? 1: -1;
        }
    }

    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes == null || envelopes.length == 0) return 0;
        Arrays.sort(envelopes, new MyComparator());
        int n = envelopes.length;
        int[] dp = new int[n];
        dp[0] = envelopes[0][1];
        int index = 0;

        for(int i = 1; i < n; i++){
            int pos = binarySearch(dp, 0, index, envelopes[i][1]);
            if(pos > index){
                dp[pos] = envelopes[i][1];
                index = pos;
            }
            dp[pos] = Math.min(dp[pos], envelopes[i][1]);
        }
        return index + 1;
    }

    private int binarySearch(int[] dp, int start, int end, int height){
        int left = start;
        int right = end;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;

            if(height < dp[mid]){
                right = mid;
            } else {
                left = mid;
            }
        }
        if(height <= dp[left]) return left;
        if(height > dp[right]) return right + 1;

        return right;
    }
}
```

## [Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/)


---

# 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://mnunknown.gitbook.io/algorithm-notes/lisff0c_dan_diao_zhan_lei/zhan_ff0c_dan_diao_zhan.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.