大厂高频算法考点--单调栈

什么是单调栈：

单调栈就是借助一个栈，在仅仅使用当前栈的条件下，时间复杂度是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;}
}