大厂高频算法考点--单调栈
什么是单调栈：
单调栈就是借助一个栈，在仅仅使用当前栈的条件下，时间复杂度是N（n）,将每个节点最有离这他最近的大于或者是小于的数据返回，将已知数组的元素放到栈里。再自我实现的代码里面我们使用数组实现栈结构，将我们的运算时间再次优化。
二.代码实现单调栈：
这个测试链接是牛客网的测试，大家可以再学习之后就测试一下。
https://www.nowcoder.com/practice/2a2c00e7a88a498693568cef63a4b7bb
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {private static int n, m,r; //n 代表数组的长度 之后的值就是数组的值 r是为了节约栈的空间，使用数组private static int[] arr = new int[1000001];private static int[] stack = newint[1000001];//栈里面仿制的是数组的下标private static int[][] ans = new int[1000001][2];public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));//不是读取一行StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));while (in.nextToken() != StreamTokenizer.TT_EOF) {n = (int)in.nval;for (int i = 0; i < n; i++) {in.nextToken();arr[i] = (int)in.nval;}compute();//开始编写核心逻辑for (int i = 0; i < n; i++) {out.println(ans[i][0] + " " + ans[i][1]);}}out.flush();out.close();br.close();}// arr[0...n-1]public static void compute() {r = 0;int cur;// 遍历阶段for (int i = 0; i < n; i++) {while(r>0&&arr[stack[r-1]]>=arr[i]){cur=stack[--r];ans[cur][1]=i;ans[cur][0]=r>0?stack[r-1]:-1;}stack[r++]=i;}// 清算阶段while (r > 0) {cur=stack[--r];ans[cur][1]=-1;ans[cur][0]=r>0?stack[r-1]:-1;}// 修正阶段// 左侧的答案不需要修正一定是正确的，只有右侧答案需要修正// 从右往左修正，n-1位置的右侧答案一定是-1，不需要修正for (int i = n - 2; i >= 0; i--) {if (ans[i][1] != -1 &&arr[ans[i][1]] == arr[i]) { ans[i][1] = ans[ans[i][1]][1];}}}
}三.单调栈类型题总结
3.1 天气状况
这是leetcode上面的一个题，测试连接如下：739. 每日温度 - 力扣（LeetCode）
给定一个整数数组
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]
这是题目的描述，我们可以尝试就是使用单调栈解决。答案如下：
class Solution {public int[] dailyTemperatures(int[] temperatures) {//创建答案数组int[] answer =new int[temperatures.length];//创建一个数组，实现栈的功能，注意这个栈实现的功能是只有比他大的时候出战int[] stack =new int[temperatures.length];int r=0;for(int i=0;i<temperatures.length;i++){int cur=0;while(r>0&&temperatures[stack[r-1]]<temperatures[i]){cur=stack[--r];answer[cur]=i-cur;}stack[r++]=i;}return answer; }}3.2：907. 子数组的最小值之和 - 力扣（LeetCode）
就是查找比它小的数在哪里，那他就是当前数组里面最小的值了 主要就是这个值在哪里呢。【1 3 4 5 2 5 7 1 2 3】【0 1 2 3 4 5 6 7 8 9】总结公式 主要的优化就是即使是相等的也不需要总结这个单调栈。因为他缺的值在后续中会补上 【1 3 4 5 6 5 7 1 2 3】 【0 1 2 3 4 5 6 7 8 9】
class Solution {public static int MOD = 1000000007;
public int sumSubarrayMins(int[] arr) {//创建栈，开始计算结果int[] stack =new int[arr.length];int r=0;int cur=0;int[][] ans=new int[arr.length][2];for(int i=0;i<arr.length;i++){while(r>0&&arr[stack[r-1]]>arr[i]){cur=stack[--r];ans[cur][1]=i;ans[cur][0]=r>0?stack[r-1]:-1;}stack[r++]=i;}while(r>0){cur=stack[--r];ans[cur][1]=arr.length;ans[cur][0]=r>0?stack[r-1]:-1;}long sum=0;for(int i=0;i<ans.length;i++){//加法的取模运算没什么特殊的sum=(sum+(long)((long)arr[i]*(long)(i-ans[i][0])*(long)(ans[i][1]-i)))%MOD;}return (int)sum;}
}方法二：
class Solution {public static int MOD = 1000000007;
public int sumSubarrayMins(int[] arr) {//创建栈，开始计算结果int[] stack =new int[arr.length];int r=0;int cur=0;long sum=0;for(int i=0;i<arr.length;i++){while(r>0&&arr[stack[r-1]]>arr[i]){cur=stack[--r];int right =i;int left=r>0?stack[r-1]:-1;//加法的取模运算没什么特殊的sum=(sum+(long)((long)arr[cur]*(long)(cur-left)*(long)(right-cur)))%MOD;}stack[r++]=i;}while(r>0){cur=stack[--r];int right =arr.length;int left=r>0?stack[r-1]:-1;sum=(sum+((long)arr[cur]*(long)(cur-left)*(long)(right-cur)))%MOD;}return (int)sum;}
}
执行用时分布 6ms 击败 98.32%
3.3：84. 柱状图中最大的矩形 - 力扣（LeetCode）
class Solution {public int largestRectangleArea(int[] heights) {//现在思考一个问题，就是这个的时间复杂度是O(N)int[] stack =new int[heights.length];int r=0;int cur=0;int ans=0;for(int i=0;i<heights.length;i++){while(r>0&&heights[stack[r-1]]>=heights[i]){cur =stack[--r];int left=r>0?stack[r-1]:-1;int right=i;ans=Math.max((right-left-1)*heights[cur],ans);}stack[r++] = i; // 把当前柱子的索引入栈}while(r>0){cur =stack[--r];int left=r>0?stack[r-1]:-1;int right=heights.length;ans=Math.max((right-left-1)*heights[cur],ans);}return ans;}
}3.4：85. 最大矩形 - 力扣（LeetCode）
思路：
首先在我们的思路里面，以每一层为底去计算面积 但是必须是连续的才会是累计关系，如果是零的话就直接为0 解释一下为什么是这样的，因为如果是0的话，你这里是组不成长方形的，所以你的结果就会和你以前计算的值相同，在这里算的话就是零，但是这是零的话，对别的点是否有影响呢，当然是不会有的 因为你这里是零，谁也不能在这里创建长方形了，不会由影响 用到的技巧是压缩数组
class Solution {public int maximalRectangle(char[][] matrix) {int ans = 0;int[] arr = new int[matrix[0].length]; // 初始化高度数组for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {// 更新 arr 数组：如果是 '1' 则增加高度，否则重置为 0arr[j] = (matrix[i][j] == '1') ? arr[j] + 1 : 0;}ans = Math.max(getSum(arr), ans); // 更新答案}return ans;}private int getSum(int[] heights){//现在思考一个问题，就是这个的时间复杂度是O(N)int[] stack =new int[heights.length];int r=0;int cur=0;int ans=0;for(int i=0;i<heights.length;i++){while(r>0&&heights[stack[r-1]]>=heights[i]){cur =stack[--r];int left=r>0?stack[r-1]:-1;int right=i;ans=Math.max((right-left-1)*heights[cur],ans);}stack[r++] = i; // 把当前柱子的索引入栈}while(r>0){cur =stack[--r];int left=r>0?stack[r-1]:-1;int right=heights.length;ans=Math.max((right-left-1)*heights[cur],ans);}return ans;}
}