单调栈

单调栈算法

单调栈是一种特殊的数据结构，分为单调递增栈和单调递减栈，保证元素从栈顶到栈底的单调性。单调栈常用于在$O(n)$的时间复杂度内寻找序列中某些元素的相邻元素，如左侧第一个更大/更小的元素等。

单调递增栈

单调递增栈的特点是从栈顶到栈底的元素是单调递增的。只有比栈顶元素小的元素才能直接进栈，否则需要先将栈中比当前元素小的元素出栈，再将当前元素入栈。这样就保证了栈中保留的都是比当前入栈元素大的值。

代码示例

def monotoneIncreasingStack(nums):

stack = []

for num in nums:

while stack and num >= stack[-1]:

stack.pop()

stack.append(num)

return stack

单调递减栈

单调递减栈的特点是从栈顶到栈底的元素是单调递减的。只有比栈顶元素大的元素才能直接进栈，否则需要先将栈中比当前元素大的元素出栈，再将当前元素入栈。这样就保证了栈中保留的都是比当前入栈元素小的值。

代码示例

def monotoneDecreasingStack(nums):

stack = []

for num in nums:

while stack and num <= stack[-1]:

stack.pop()

stack.append(num)

return stack

应用场景

单调栈可以在时间复杂度为$O(n)$的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素。常见的应用场景包括：

1. 寻找左侧第一个比当前元素大的元素：从左到右遍历元素，构造单调递增栈。

2. 寻找左侧第一个比当前元素小的元素：从左到右遍历元素，构造单调递减栈。

3. 寻找右侧第一个比当前元素大的元素：从右到左遍历元素，构造单调递增栈。

4. 寻找右侧第一个比当前元素小的元素：从右到左遍历元素，构造单调递减栈。

实际问题示例

下一个更大元素

给定两个没有重复元素的数组_nums1_和_nums2_，其中_nums1_是_nums2_的子集。要求找出_nums1_中每个元素在_nums2_中的下一个比其大的值。

代码示例

class Solution:

def nextGreaterElement(self, nums1, nums2):

res = []

stack = []

num_map = {}

for num in nums2:

while stack and num > stack[-1]:

num_map[stack.pop()] = num

stack.append(num)

for num in nums1:

res.append(num_map.get(num, -1))

return res

通过以上代码和示例，可以看出单调栈在解决某些特定问题时非常高效，能够将时间复杂度从$O(n^2)$降低到$O(n)$