单调栈(LeetCode-下一个更大元素)

每日一题

今天刷到了一道用到单调栈来解决的题目,想到自己没有总结过单调栈的知识点,因此想总结一下。

介绍

什么是单调栈?

单调栈的定义其实很简单,所谓单调栈就是指一个单调递增或是单调递减的栈。

那单调栈有什么用呢?

单调栈通常用来在一串数字(例如数组)中,找到某个数字的左侧或是右侧最近的大于或小于这个数字的数。

那么是如何实现的呢?

如果想要在一个数组中找到一个数字右侧大于它本身的第一个数,就可以使用一个单调递增的栈来实现。

可以从后向前遍历该数组,,如果此时单调栈为空那么将该数字压入栈,如果栈中不为空且当前遍历到数大于栈顶的数字,那么就会将栈顶的数字弹出栈,如果栈中的数一直小那就一直弹出,因为我们要维护这个从上到下递增的栈。这样对于每一个数来说,当轮到这个数的时候,在判断栈顶数字并弹出后,如果弹出后栈为空,那就证明这个数字后没有它本身大的数字。如果栈中还有数字,那么栈顶的元素就是该数字右侧第一个比他大的数字。因为比他的数字不会被弹出,并且遍历从后向前,这个数字一定是右侧最近的。

这个情况说完后,其他的情况也是一样的。

例题

来看力扣496题——下一个最大元素。

题目要求

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ,下标从 0 开始计数,其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ,找出满足 nums1[i] == nums2[j] 的下标 j ,并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素,那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案,满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1:

输入:nums1 = [4,1,2], nums2 = [1,3,4,2].
输出:[-1,3,-1]
解释:nums1 中每个值的下一个更大元素如下所述:
- 4 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。
- 1 ,用加粗斜体标识,nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。

示例 2:

输入:nums1 = [2,4], nums2 = [1,2,3,4].
输出:[3,-1]
解释:nums1 中每个值的下一个更大元素如下所述:
- 2 ,用加粗斜体标识,nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ,用加粗斜体标识,nums2 = [1,2,3,4]。不存在下一个更大元素,所以答案是 -1 。

题目解析

该题是要我们找到一个数组num2的子数组num1中的数在num2中右侧最近的一个大于它的数,如果不存在就返回-1,存在就保存这个数,最后将这些数放在数组中。这个一个典型的单调栈问题,我们可以通过我上面提到的方法找到num2数组中的每个数右侧第一个大于本身的数并将其存在一个map中,最后通过遍历num1数组在map中找到对应的数字并存入数组。

下面我们来图文解释一下示例1中的情况

首先遍历数组,第一个数字——2,目前栈是空的,得到-1.将2压入栈

下面是4,2小于4.因此将2弹出,此时栈空得到-1,压入4

下面轮到3,3小于4,因此没有弹出操作,得到4,将3也压入栈

最后轮到1,1也小于3,因此不会弹出,得到3,并将1压入栈。

至此遍历结束我们得到了全部的数据并将其存入map中

1—— 3

3—— 4

4—— -1

2—— -1

最后遍历num1数组,拿到结果[-1,3,-1]

代码实现

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new HashMap<>();
        Deque<Integer> stack  = new ArrayDeque<Integer>();
        for(int i =nums2.length-1;i>=0;i--){
            int num = nums2[i];
            while(!stack.isEmpty()&&num>=stack.peek()){
                stack.pop();
            }
        
            if(stack.isEmpty()){
                map.put(num,-1);   
            }else{
                map.put(num,stack.peek());
            }
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for(int i=0;i<nums1.length;i++){
            res[i] = map.get(nums1[i]);
        }
        return res;

    }
}

结果

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/527229.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

CSS层叠样式表学习(基础选择器)

&#xff08;大家好&#xff0c;今天我们将继续来学习CSS&#xff08;2&#xff09;的相关知识&#xff0c;大家可以在评论区进行互动答疑哦~加油&#xff01;&#x1f495;&#xff09; 目录 二、CSS基础选择器 2.1 CSS选择器的作用 2.2 选择器分类 2.3 标签选择器 2.…

Windows系统下安装java开发环境所需的JDK开发工具包

目录 一、JDK开发工具包下载二、安装三、环境变量配置3.1 添加安装包路径3.2 添加lib路径3.3 添加bin目录 四、检查是否安装成功五、总结 一、JDK开发工具包下载 官网地址&#xff1a;JDK下载 打开网址后有多个版本的JDK&#xff0c;学者根据自己电脑需求选择对应版本下载。如…

精酿啤酒:传统酿造与现代工艺的结合

在啤酒酿造领域&#xff0c;传统酿造与现代工艺的结合是提品质和生产效率的重要途径。Fendi Club啤酒在酿造过程中&#xff0c;巧妙地将传统酿造工艺与现代技术相结合&#xff0c;为消费者带来了品质的啤酒体验。 Fendi Club啤酒注重传统的天然原料选择。他们坚持使用大麦、啤酒…

免费云服务器汇总,最长永久免费使用

随着云计算技术的快速发展&#xff0c;越来越多的企业和个人开始将业务迁移到云端。云服务器作为云计算的重要组成部分&#xff0c;以其灵活、高效、可扩展等特点受到广泛关注。然而&#xff0c;许多人在初次接触云服务器时&#xff0c;可能会对高昂的价格望而却步。为了帮助大…

day76 jquery

知识点: 1 在HTML中引入jQuery 2 jQuery中就绪函数 3 jQuery中选择器 4 使用jQuery获取表单元素的值 及标签中间的内容 5 jQuery中获取标签属性 6 jQuery设置和获取标签样式 ----------------------------------- 一 在HTML中引入jQuery 1 1) 把jQue…

工作这么久,你有测试思维了吗?

在如今竞争激烈的职场中&#xff0c;拥有测试思维已成为一个不可或缺的技能。无论你是从事软件开发、项目管理还是市场营销等各行各业&#xff0c;测试思维都能够帮助你更好地解决问题、提高工作效率以及保障质量。然而&#xff0c;工作时间的长短并不代表一个人是否具备测试思…

python ConfigParser:Python 标准库,ini 文件解析器

大家好&#xff01;在进行接口自动化工作时&#xff0c;配置文件是非常常见和重要的一部分。Python 提供了一个强大的标准库——ConfigParser&#xff0c;用于解析和处理 INI 文件。在本文中&#xff0c;我们将介绍如何使用 ConfigParser 来读取和操作 INI 文件&#xff0c;并提…

【Linux进阶之路】ARP欺骗实验

正文 话不多说&#xff0c;直接干&#xff01; 首先我们需要准备一下环境&#xff0c;先配置VMARE&#xff0c;然后下载KALI的虚拟机。 详细的安装教程视频&#xff1a;点击跳转&#xff0c;下载KALI可能要半个小时&#xff0c;中间可以看个剧玩个游戏缓一缓。 配置好之后&am…

ArcGIS和ArcGIS Pro快速加载ArcGIS历史影像World Imagery Wayback

ArcGIS在线历史影像网站 World Imagery Wayback(网址:https://livingatlas.arcgis.com/wayback/)提供了数期历史影像在线浏览服务,之前不少自媒体作者在文中宣称其能代表Google Earth历史影像。 1、一点对比 (1)同一级别下的版本覆盖面 以下述区域为例,自2014年2月20…

提升自媒体写作效率:7款必备工具推荐! #知识分享#媒体#AI写作

我们做自媒体运营&#xff0c;想要快速的创作内容&#xff0c;提供文章的创作速度是我们的目标&#xff0c;我们别的大佬可以很快地就创作出一篇内容&#xff0c;而自己墨迹半天确出不了一个字呢&#xff1f;其实这关乎到创作技巧&#xff0c;下面小编就跟大家分享如何利用自媒…

OneFlow深度学习框架:技术优势与功能特点

文章目录 一、概要二、核心技术优势2.1、分布式训练2.2、极致性能2.3、端到端的智能数据平台2.4、开放灵活的算法支持2.5、跨平台支持 三、功能特点四、OneFlow与TensorFlow对比四、安装OneFlow五、总结 一、概要 OneFlow是一款基于Python的开源深度学习框架&#xff0c;旨在实…

简介有向无环图DAG

Sui创纪录的每秒交易量部分归功于数学构造&#xff0c;即有向无环图&#xff08;Directed Acyclic Graph&#xff0c;DAG&#xff09;&#xff0c;该构造通过以最高效的方式处理交易来加速网络交易&#xff0c;而不是按照先来先服务的线性进展。 区块链是设计用于确保数据完整…

【简单讲解下Lisp的学习历程】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

模型融合的方法

集成学习&#xff1a;通过构建并结合多个学习器来完成学习任务&#xff0c;有时也被称为多分类器系统、基于委员会的学习等。&#xff08;集成学习不是只有同质学习器的集成&#xff0c;还有异质学习器的集成&#xff09; 模型融合&#xff1a;通过多个模型共同决策提升任务的…

代码随想录学习Day 25

491.递增子序列 题目链接 讲解链接 本题的是求自增子序列&#xff0c;所以不能对原数组进行排序&#xff0c;排完序的数组都是自增子序列了&#xff0c;所以不能使用之前的去重逻辑&#xff01;如果仍旧使用之前的逻辑&#xff0c;那么当遇到数组为{4&#xff0c;7&#xff…

思迈特软件与上海德拓签署战略合作协议,携手赋能企业数字化转型

3月27日&#xff0c;广州思迈特软件有限公司&#xff08;简称“思迈特软件”&#xff09;与上海德拓信息技术有限公司&#xff08;简称“德拓信息”&#xff09;正式签约建立战略合作伙伴关系。双方将在数字化转型、数据服务、数据应用以及市场资源等多个领域展开深度合作&…

2024年贵州省职业院校技能大赛云计算应用赛项赛题第2套

#需要资源&#xff08;软件包及镜像&#xff09;或有问题的&#xff0c;可私聊博主&#xff01;&#xff01;&#xff01; #需要资源&#xff08;软件包及镜像&#xff09;或有问题的&#xff0c;可私聊博主&#xff01;&#xff01;&#xff01; #需要资源&#xff08;软件包…

xilinx AXI CAN驱动开发

CAN收发方案有很多&#xff0c;常见的解决方案通过是采用CAN收发芯片&#xff0c;例如最常用的SJA1000,xilinx直接将CAN协议栈用纯逻辑实现&#xff0c;AXI CAN是其中一种&#xff1b; 通过这种方式硬件上只需外接一个PHY芯片即可 上图加了一个电平转换芯片 软件设计方面&…

【Labview】虚拟仪器技术

一、背景知识 1.1 虚拟仪器的定义、组成和应用 虚拟仪器的特点 虚拟仪器的突出特征为“硬件功能软件化”&#xff0c;虚拟仪器是在计算机上显示仪器面板&#xff0c;将硬件电路完成信号调理和处理功能由计算机程序完成。 虚拟仪器的组成 硬件软件 硬件是基础&#xff0c;负责将…

提取COCO数据集中特定的类—vehicle 4类

提取COCO数据集中特定的类—vehicle 4类 1 安装pycocotools2 下载COCO数据集3 提取特定的类别4 多类标签合并 1 安装pycocotools pycocotools github地址 pip install githttps://github.com/philferriere/cocoapi.git#subdirectoryPythonAPI2 下载COCO数据集 COCO官网下载2…