【Leetcode】单调栈

news/2024/10/31 23:22:56/

单调栈

单调栈是一种高效的栈结构,常用来解决数组中元素顺序相关的问题,如“下一个更大元素”等。其核心思想是通过维护栈内元素的单调性,并记录元素的间顺序关系,以减少不必要的比较操作。通常情况下,由于每个元素入栈和出栈各一次,时间复杂度为 O(n)。

在使用过程中,需要关注两个重点,分别是栈顶元素的弹出条件和预期目标的结果收集,具体而言:

  • 弹出条件:满足什么条件时栈顶元素弹出。这往往取决于何时可以得到目标结果,这也可以用于判断应该使用单调增栈还是单调减栈。
  • 结果收集:预期的目标结果如何收集。对于简单的问题,目标结果往往可以直接得到,而对于稍复杂的问题,如接雨水等,则需要进行一定的计算和转换。

如何确定这两点呢?我们将关注点放在栈顶,当有元素入栈时,判断是否可以找到栈顶元素的目标结果,如果找到了,就满足触发条件,接着就可以收集目标结果并弹出栈顶元素。

另外,在单调栈的使用时,通常使用元素的索引进行栈操作,这是因为索引中附带了元素的值和位置信息,以便进行较复杂的操作。

下面从一些经典例题出发,由浅入深地介绍单调栈的使用。

例题 1:下一个更大元素(基础)

问题描述: 在一个没有重复值的数组中,找到每个元素右侧第一个比它大的元素。

基本思路:将数组元素依次压入单调栈中,判断入栈元素是否比栈顶元素大,当比栈顶元素大时,即找到了栈顶元素的下一个更大元素,栈顶元素弹出并收集目标结果。

  • 触发条件:当入栈元素大于栈顶元素时,找到了栈顶元素的下一个更大元素,栈顶元素弹出。
  • 结果收集:栈顶元素弹出时,收集待入栈元素,即为栈顶元素的下一个更大元素。

![[attachments/<a class=单调栈-下一个更大元素.svg]]" />

练习 1.1:leetcode.cn/problems/next-greater-element-i/description/" rel="nofollow">496. 下一个更大元素 I - 力扣(LeetCode)(简单)
# 496. 下一个更大元素 I
# https://leetcode.cn/problems/next-greater-element-i/description/
def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:# 单调栈# 将nums2转化为字典,通过单调栈找到下一个更大元素st = []ans = {n:-1 for n in nums2}for n in nums2:while st and n > st[-1]:ans[st.pop()] = nst.append(n)return [ans[n] for n in nums1]
练习 1.2:leetcode.cn/problems/next-greater-element-ii/description/" rel="nofollow">503. 下一个更大元素 II - 力扣(LeetCode)(简单)
# 503. 下一个更大元素 II
# https://leetcode.cn/problems/next-greater-element-ii/description/
def nextGreaterElements(nums: List[int]) -> List[int]:# 单调栈,# 索引操作,通过取余实现循环索引n = len(nums)ans = [-1]*nst = []for i in range(2*n):idx = i%nwhile st and nums[idx] > nums[st[-1]]:ans[st.pop()] = nums[idx]st.append(idx)return ans
练习 1.3:leetcode.cn/problems/number-of-visible-people-in-a-queue/description/" rel="nofollow">1944. 队列中可以看到的人数 - 力扣(LeetCode)(中等)

|425

问题描述:返回队列中每个人在他右侧能看到的人数

基本思路:当前位置可以观察到的最远位置是下一个更大值,但由于存在遮挡问题(如 5 夹在 8 和 11 之间),观察时不会被看到。因此,按照下一个更大值的思路,并不能剔除被遮挡的元素,因此按照下一个更大值的做法行不通。
转换一下思路,从当前位置往左可以被哪些位置看到呢——上一个更小值,此时只需要确保从当前位置往左依次递减,当遇到栈顶的更大值时,栈顶元素弹出,就可以确保元素被正确统计。需要注意,这里的栈顶元素是被看到的元素,而入栈元素是需要统计的。

  • 触发条件:当入栈元素大于栈顶元素时,非单调递减,即找到了当前元素可看到的一个元素,栈顶元素弹出。
  • 结果收集:栈顶元素代表入栈元素可以看到的元素,当栈顶元素弹出时,将入栈元素可看到的人数加 1。另外需要注意的是,当栈不为空时,栈顶元素也可以被当前元素看到,需要再加 1。

在这里插入图片描述

# 1944. 队列中可以看到的人数
# https://leetcode.cn/problems/number-of-visible-people-in-a-queue/description/
def canSeePersonsCount(heights: List[int]) -> List[int]:# 单调栈,从末端开始的单调递减栈# i位置能看到的是右侧单调增且不被遮挡的元素数量n = len(heights)st = []ans = [0]*nfor i in range(n-1,-1,-1):while st and heights[i] > heights[st[-1]]:st.pop()ans[i] += 1 # 统计入栈元素可看到的人数# 栈不为空时,栈顶元素也可以被看到ans[i] += 1 if st else 0st.append(i)return ans

http://www.ppmy.cn/news/1543429.html

相关文章

Java8 实战阅读笔记

文章目录 1. Java 8、9、10以及11的变化1.1 为什么变化1.2 Java 为什么还在变1.3 Java 中的函数1.4 流 2. 通过行为参数化传递代码2.1 应对不断变化的需求2.2 行为参数化2.3 对付啰嗦2.3.1 匿名类2.3.2 Lambda 表达式2.3.4 List 类型抽象化 3. Lambda 表达式3.1 Lambda 管中窥豹…

Paimon x StarRocks 助力喜马拉雅构建实时湖仓

作者&#xff1a;王琛 喜马拉雅数仓专家 小编导读&#xff1a; 本文将介绍喜马拉雅直播的业务现状及数据仓库架构的迭代升级&#xff0c;重点分享基于 Flink Paimon StarRocks 实现实时湖仓的架构及其成效。我们通过分钟级别的收入监控、实时榜单生成、流量监测和盈亏预警&am…

面试题:JVM(二)

1. 面试题 简述 Java 类加载机制?&#xff08;百度&#xff09; JVM类加载机制 &#xff08;滴滴&#xff09; JVM中类加载机制&#xff0c;类加载过程&#xff0c;什么是双亲委派模型&#xff1f; &#xff08;腾讯&#xff09; JVM的类加载机制是什么&#xff1f; &#x…

【网络】传输层协议TCP(中)

目录 四次挥手状态变化 流量控制 PSH标记位 URG标记位 四次挥手状态变化 之前我们讲了四次挥手的具体过程以及为什么要进行四次挥手&#xff0c;下面是四次挥手的状态变化 那么我们下面可以来验证一下CLOSE_WAIT这个状态&#xff0c;这个状态出现的条件是后调用close的一方…

传输层TCP

报头 1.报头和有效载荷如何分离将&#xff0c;有效载荷向上交付&#xff1f; tcp有个标准报头长度为20&#xff0c;那是不是以为我们可以像udp一样分离依靠报头大小去分离&#xff0c;我们仔细去看我们报头中还有个选项没包含到。 我们还有个首部长度&#xff0c;四位可以表…

[Linux关键词]unmask,mv,dev/pts,stdin stdout stderr,echo

希望你开心&#xff0c;希望你健康&#xff0c;希望你幸福&#xff0c;希望你点赞&#xff01; 最后的最后&#xff0c;关注喵&#xff0c;关注喵&#xff0c;关注喵&#xff0c;大大会看到更多有趣的博客哦&#xff01;&#xff01;&#xff01; 喵喵喵&#xff0c;你对我真的…

Java审计对比工具JaVers使用

最近有个需求&#xff0c;需要将页面的内容生成excel或者word文档&#xff0c;而且每次的修改都需要生成新的版本&#xff0c;同时需要记录每次修改变化的内容。我们会把每次的修改的内容提交赋值给一个java对象&#xff0c;同时存储到数据库一条新数据&#xff0c;对应数据表一…

物联网海量数据下的时序数据库选型:InfluxDB、TDEngine、MongoDB与HBase对比与建议

随着物联网&#xff08;IoT&#xff09;的普及&#xff0c;各行业纷纷部署大量传感器、设备生成的数据流&#xff0c;面对如此海量的时间序列数据&#xff0c;如何高效存储、查询和分析成为关键。为此&#xff0c;时序数据库&#xff08;Time Series Database, TSDB&#xff09…