单调栈总结

自底向上的单调递减栈，一般用来寻找下一个更大的元素。
常见做法是从后往前遍历数组，栈顶元素如果小于当前元素就出栈，保持单调性

def nextGreaterElements(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        stack = []
        res = [-1]*n 
        for i in range(n-1,-1,-1):
            while stack and stack[-1] <= nums[i]:
                stack.pop()
            if stack:
                res[i] = stack[-1]
            stack.append(nums[i])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

自底向上的单调递增栈，一般用来寻找前一个更小的元素。
常见做法是从前往后遍历数组，栈顶元素如果大于当前元素就出栈，保持单调性

def lastMinerElements(self, nums):
res = [-1]*n 
stack = []
for i in range(len(nums)):
    while stack and  nums[i] < stack[-1]:
        stack.pop()
    if stack:
        res[i] = stack[-1]
    stack.append(nums[i)
return res 
1
2
3
4
5
6
7
8
9
10