力扣题目：#503.下一个更大元素II
刷题时长：参考题解后2min
解题方法：单调栈
复杂度分析
- 时间O(n)
- 空间O(n)
问题总结文章来源：https://www.toymoban.com/news/detail-535280.html
- 如何解决环的问题
本题收获文章来源地址https://www.toymoban.com/news/detail-535280.html
- 循环数组解决方案
- 思路一：将两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了
- 思路二：不扩充nums，而是在遍历的过程中模拟走了两遍nums
for i in range(1, len(nums)*2): if nums[i%len(nums)] <= nums[stack[-1]]: stack.append(i%len(nums)) else: while stack and nums[i%len(nums)] > nums[stack[-1]]: ans[stack[-1]] = nums[i%len(nums)] stack.pop() stack.append(i%len(nums))
力扣题目：#42. 接雨水
刷题时长：参考题解后10min
解题方法：单调栈
复杂度分析
- 时间O(n)
- 空间O(n)
问题总结
- 当遍历元素大于栈内元素时，处理完计算后，仍需将当前遍历的元素压入栈
本题收获
- 其他思路：暴力解法和双指针解法
- 单调栈思路：利用单调栈找到凹槽，按照行方向来计算雨水
- 单调栈内元素的顺序：口小底大。一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子
- 遇到相同的元素：更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中
到了这里，关于力扣算法刷题Day59｜单调栈的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
