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. 代码