|
|
单调栈问题：
要想知道单调的堆栈适合解决什么问题，首先要知道单调的堆栈的作用。单调堆栈分为单调增量堆栈和单调减少堆栈，使用单调堆栈可以访问下一个较大(较小)的元素(或示例)。
也就是说，当需要比较队列或数组中前后元素的大小关系来解决问题时，通常使用单调的堆栈。下面简要介绍单调堆栈和单调堆栈问题，详细说明使用单调堆栈处理问题的过程。
什么时候使用单调栈？
通常是一维阵列，在所有元素的右侧(左侧)找到比自己大的(小)第一个元素，并要求O(n)的时间复杂性
单调栈原理：
单调增量堆栈：从堆栈底部增加到堆栈顶部，堆栈顶部较大
单调递减堆栈：从堆栈底部减少到堆栈顶部，堆栈顶部较小
python模板套路：
1):当前项目向右找到第一个比自己大的位置3354，从右到左保持单调的减少堆栈。
def nextgreaterelement _ 01(nums 3360列表)3360
长度=len (nums)
Res，stack=[-1] *长度，[]
For I inrange(长度-1，
pan> -1, -1):
while stack and stack[-1] nums:
stack.pop()
if stack:
res = stack[-1]
stack.append(nums)
return res
或者 当前项向右找第一个比自己大的位置 —— 从左向右维护一个单调递减栈。
def nextGreaterElement_011(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length):
while stack and nums[stack[-1]] nums:
idx = stack.pop()
res[idx] = nums
stack.append(i)
return res
2)：当前项向右找第一个比自己小的位置 —— 从右向左维护一个单调递增栈
def nextGreaterElement_02(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length - 1, -1, -1):
while stack and stack[-1] >= nums:
stack.pop()
if stack:
res = stack[-1]
stack.append(nums)
return res
3): 当前项向左找第一个比自己大的位置 —— 从左向右维护一个单调递减栈
def nextGreaterElement_03(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length):
while stack and stack[-1] nums:
stack.pop()
if stack:
res = stack[-1]
stack.append(nums)
return res
4): 当前项向左找第一个比自己小的位置 —— 从左向右维护一个单调递增栈
def nextGreaterElement_04(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length):
while stack and stack[-1] >= nums:
stack.pop()
if stack:
res = stack[-1]
stack.append(nums)
return res
参考来源：https://leetcode-cn.com/problems/next-greater-element-i/solution/dan-diao-zhan-zong-jie-by-wu-xian-sen-2/
|
|
发表于 2021-3-7 14:33:01
