当前位置: 首页 > news >正文

【Leetcode】单调栈

单调栈

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

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

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

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

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

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

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

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

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

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

![[attachments/单调栈-下一个更大元素.svg]]

练习 1.1: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: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: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.mrgr.cn/news/62908.html

相关文章:

  • [Web安全 网络安全]-提权、开发、对抗
  • 双十一数码好物怎么选?五大高性能数码好物快览!
  • AI学习指南自然语言处理篇-Transformer模型简介
  • [ 问题解决篇 ] 新装虚拟机 Windows server 2012 无法 ping 通(关闭/开启防火墙详解)
  • 天润融通突破AI客服局限,三大关键提升文本机器人问答效果
  • ELK之路第四步——整合!打通任督二脉
  • 强化学习DQN实践(gymnasium+pytorch)
  • 人工智能生产力悖论:为什么大多数人没用上AI工具?
  • 得物App获评新奖项,正品保障夯实供应链创新水平
  • 今年双11,拼多多吹“新”风
  • tinyint数据库类型
  • SPA——MVC 与 MVVM - 2024最新版前端秋招面试短期突击面试题【100道】
  • 【测试工具】通过Jmeter压测存储过程
  • Git学习记录
  • 14. 不修改数组找出重复的数字
  • 【论文速读】Optimization-based Prompt Injection Attack to LLM-as-a-Judge
  • Python 从入门到实战43(Pandas数据结构)
  • 哈希函数简介
  • 【调试记录】CARLA车辆actor设置BehaviorAgent自动规划后不沿道路行驶
  • Terraform Provider 加速方案
  • 什么是 Spring Cloud Bus?我们需要它吗?
  • 【AI日记】24.10.31 学习LangChain和寻找AI研究报告(比如麦肯锡)
  • ROS(快速初步入门)
  • 谷歌Google搜索广告账户代理开户!
  • iDP3复现代码运行逻辑全流程(一)——部署全流程代码逻辑梳理(Learning)
  • python opencv1