欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 艺术 > leetcode刷题-单调栈

leetcode刷题-单调栈

2025/5/10 10:54:16 来源:https://blog.csdn.net/emmmmXxxy/article/details/147015146  浏览:    关键词:leetcode刷题-单调栈

代码随想录单调栈|739. 每日温度、496.下一个更大元素 I、503.下一个更大元素II、42. 接雨水、84.柱状图中最大的矩形

    • 739. 每日温度
    • 496.下一个更大元素 I
    • 503.下一个更大元素II
    • 42. 接雨水 -- 面试常考题
    • 84.柱状图中最大的矩形

739. 每日温度

leetcode题目链接
代码随想录文档讲解

思路

找到这个元素后面 第一个比这个元素大的元素,算它们的距离(下标之差)
暴力解法:时间复杂度n2
单调栈:时间复杂度n2
单调栈适合:求当前元素左边(右边)比当前元素大(小)的元素
单调栈中存放的是下标,存放的元素是递增(从栈顶到栈底)还是递减呢?递增(第一个比它大的元素),递减(第一个比它小的元素)

单调栈的作用: 记录遍历过的元素!!

python代码

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:answer = [0]*len(temperatures)stack = [0] # 存放下标for i in range(1, len(temperatures)):if temperatures[i] <= temperatures[stack[-1]]:stack.append(i)else:while len(stack) != 0 and temperatures[i] > temperatures[stack[-1]]:answer[stack[-1]] = i - stack[-1]stack.pop()stack.append(i)return answer

496.下一个更大元素 I

leetcode题目链接
代码随想录文档讲解

思路

本题本质还是对nums2采用单调栈的算法计算下一个最大元素,但是返回的result需要和nums1大小一致,顺序一致,因此对nums2中的元素计算完后需要映射回nums1,除此之外,本题的result数组应该初始化为-1

两个没有重复元素 的数组 nums1 和 nums2,采用map进行映射,使用哈希表数据结构,但是对于python实现,可以使用index函数

python代码
python index函数
nums1 = [1, 3, 5, 7]
nums1.index(5) 输出: 2

class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:result = [-1]*len(nums1)stack = [0]for i in range(1, len(nums2)):if nums2[i] <= nums2[stack[-1]]:stack.append(i)else:while len(stack)!= 0 and nums2[i] > nums2[stack[-1]]:if nums2[stack[-1]] in nums1: # 这里注意不要写反了,nums2[stack[-1]]和nums2[i]index = nums1.index(nums2[stack[-1]])result[index] = nums2[i]stack.pop()stack.append(i)return result

503.下一个更大元素II

leetcode题目链接
代码随想录文档讲解

思路

本题相比前面两题,变为循环数组了(数组可以首尾相连了)

思路1: 扩容,两个数组拼在一起,然后单调栈
例如:nums = [1,2,1],扩容后:nums = [1,2,1,1,2,1]
result = [2,-1,2,2,-1,_] 取前3个即:[2,-1,2]

思路2: 用取模的方式模拟转圈的过程 (设计成环都可以这么操作)
for i in range(len(nums)*2):
i = i%len(nums)
遍历时对数组长度×2,然后实际再进行取模,所以在超出数组长度的时候,i又回来了

python代码

n = [1, 2, 3]
n*2 输出:[1, 2, 3, 1, 2, 3]
n+n 输出:[1, 2, 3, 1, 2, 3]

# 思路1
class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:n = len(nums)nums = nums*2result = [-1]*len(nums)stack = [0]for i in range(1, len(nums)):if nums[i] <= nums[stack[-1]]:stack.append(i)else:while len(stack) != 0 and nums[i] > nums[stack[-1]]:result[stack[-1]] = nums[i]stack.pop()stack.append(i)res = result[:n]return res
# 思路2
class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:result = [-1]*len(nums)stack = [0]for i in range(1, len(nums)*2):i = i%len(nums)if nums[i] <= nums[stack[-1]]:stack.append(i)else:while len(stack) != 0 and nums[i] > nums[stack[-1]]:result[stack[-1]] = nums[i]stack.pop()stack.append(i)return result

42. 接雨水 – 面试常考题

leetcode题目链接
代码随想录文档讲解

思路

思路1: 暴力解法,复杂度n2
两层for循环,外层for循环一个遍历柱子,里层for循环 去找每个柱子右边比它高的第一个柱子高度及左边比它高的第一个柱子的高度是多少

思路2: 双指针优化,复杂度O(n)
提前预处理两个数组

思路3: 单调栈
这里可以借助单调栈的特性,栈内的元素是单调递增的,因此在获得了某一个元素的右边第一个比它大的元素,那么栈里的下一个元素就是左边第一个比它大的元素
栈中还是存放下标

python代码

class Solution:def trap(self, height: List[int]) -> int:result= 0stack= [0]for i in range(1, len(height)):if height[i] <= height[stack[-1]]:stack.append(i)else:while stack and height[i] > height[stack[-1]]:mid = stack.pop()if stack:w = i - stack[-1] - 1h = min(height[i], height[stack[-1]]) - height[mid] # 第一次提交把这里重命名为height了,调试了半天。。result += w*hstack.append(i)return result

84.柱状图中最大的矩形

leetcode题目链接
代码随想录文档讲解

思路

和接雨水题目遥相呼应,一个是求柱子外面的,一个是求柱子里面的

  1. 思路1: 暴力解法,复杂度n2
    两次for循环
    以某个柱子为中心,找左边比它矮的,右边比它矮的,确定高,然后根据距离确定宽

  2. 思路2: 双指针法

  3. 思路3: 单调栈
    此处的单调栈是单调递减的,因为要找左边和右边第一个比它小的,中间就是大于等于它的,高度就是当前柱子的高度,宽度为中间柱子的宽度;
    首位加0,(尾部加0)避免[2,4,6,8]这样单调递增的数组;(头部加0)对于[8,6,4,2]若满足当前元素大于栈顶元素,弹出后,栈为空,则不会进行计算面积,避免栈为空的情况

python代码

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:heights = [0] + heights + [0] # 或者 heights.insert(0, 0) heights.append(0)result = 0stack = [0]for i in range(1, len(heights)):if heights[i] >= heights[stack[-1]]:stack.append(i)else:while stack and heights[i] < heights[stack[-1]]:mid = stack.pop()if stack:w = i - stack[-1] - 1h = heights[mid]result = max(result, w*h)stack.append(i) # 第一次忘记了这行代码return result

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词