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

🕗 发布于 2024-10-20 08:31 java 开发语言

什么是单调栈：

单调栈就是借助一个栈，在仅仅使用当前栈的条件下，时间复杂度是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 = new
    int[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' 则增加高度，否则重置为 0
                arr[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;
    }
}

原文地址：https://blog.csdn.net/hdk5855/article/details/143082629

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：小红书Android面试题汇总及参考答案
下一篇：大模型~合集13

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20