8. 单调栈

有个数组arr, 找到arr[i]左面比他小的第一个数, 和右面比他小的第一个数,要求O(N)的时间复杂度.

思路：栈底下栈顶从小到大，栈中存放位置信息，入栈或者出栈的时候可能需要记录信息。

8.1 每日温度

https://leetcode.cn/problems/daily-temperatures/

1. 题目

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]

2. 思路

用一个栈来维护天气，当第i个天气比peek大的时候，出栈，并且记录当前的结果。直到栈为空或者第i个天气比peek小（while结束），入栈

3. 代码

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length];
        Deque<Integer> sk = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
            // 出栈条件：栈不为空，并且当前值比栈顶大
            while(!sk.isEmpty() && temperatures[i] > temperatures[sk.peek()]){
                // System.out.println(temperatures[i]);
                // 
                ans[sk.peek()] = i - sk.peek();
                sk.pop();
            }
            sk.push(i);
        }
        return ans;
    }
}

8.2 柱状图中最大矩阵

1. 题目

https://leetcode.cn/problems/largest-rectangle-in-histogram/

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例1：

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例2：

输入： heights = [2,4]
输出： 4

2. 思路

严格递增的栈来存储

找左右两个方向上第一个比自己小的值

入栈的时候确定第i位置的最左位置（就是peek，因为他比最左大，并且比左面大），出栈的时候，确定当前peek的最右位置（因为出栈，所以第i位置的数比peek大，并且在右面）。

最后剩下的数说明，他们在最右侧没有比他小的了，弹栈并且，最右侧的值为len

3. 代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        // 左边界位置
        int[] leftPos = new int[len];
        int[] rightPos = new int[len];
        // 单调栈 碰到小的出栈 栈内：4 5 6 ；2
        Stack<Integer> pos = new Stack<>();
        // 标记位置，防止出现xx情况
        pos.push(-1);
        int maxArea = 0;
        for(int i = 0; i < len; i++){
            while(pos.peek() != -1 && heights[pos.peek()] >= heights[i]){
               int curPos = pos.peek();
               int area = heights[curPos]*(i-leftPos[curPos]-1);
               if(area>maxArea) maxArea = area;
               pos.pop();
            }

            leftPos[i] = pos.peek();
            pos.push(i);
        }

        // 栈内弹出 -- 右边界是自己
        while(pos.peek() != -1){
            int curPos = pos.peek();
            int area = heights[curPos]*(len - leftPos[curPos]-1);
            if(area>maxArea) maxArea = area;
            pos.pop();
        }
        
        return maxArea;

    }
}

8.3 矩阵中最大矩形

1. 题目

https://leetcode.cn/problems/PLYXKQ/

给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。

注意：此题 matrix 输入格式为一维 01 字符串数组。

示例1：

输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。

示例2：

输入：matrix = []
输出：0

示例3：

输入：matrix = ["0"]
输出：0

示例4：

输入：matrix = ["1"]
输出：1

示例5：

输入：matrix = ["00"]
输出：0

2. 思路

先统计每一行，左侧相邻的1的个数。

比如某一行1 0 1 1 0 1 1左侧相邻1的个数分别为 1 0 1 2 0 1 2

之后

方法1 ：遍历矩阵O(mn)，以遍历的点为右下角，向上看用O(N)的复杂度找到当前的最大面积。 总计O(m^2n)。

方法2 ： 一次只看某一列，利用单调栈来求这一列的“面积”。在生成之后，才进行面积计算O(mn) + O(mn) = O(m*n)。

而后同8.2一样，利用单调栈，从右往左而后从左往右两次遍历得到结果。

3. 代码