单调栈#

单调栈是一种特殊的栈结构，通常用于解决“下一个最值”问题。
通过维护栈内元素的单调性，可以高效地找到满足条件的元素。
常见应用场景包括：查找下一个更大/小的元素、计算区间最大值等。
核心思想是：当新元素到来时，比较它与栈顶元素的大小关系，决定是否出栈或入栈。
时间复杂度通常为 $O(n)$ ，因为每个元素最多入栈和出栈一次。
空间复杂度为 $O(n)$ ，用于存储栈元素。

单调栈模板#

1
def calculateGreaterElement(nums):
2
    n = len(nums)
3
    res = [0] * n  # 存放答案的数组
4
    s = []  # 单调栈
5
    for i in range(n - 1, -1, -1):  # 倒序遍历
6
        while s and s[-1] <= nums[i]:
7
            s.pop()  # 矮个起开，反正也被挡着了
8
        res[i] = -1 if not s else s[-1]  # 当前元素的下一个更大元素
9
        s.append(nums[i])
10
    return res

LeetCode 739. 每日温度#

题目链接

1
class Solution:
2
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
3
        n = len(temperatures)
4
        res = [0] * n
5
        stack = []
6
        for i in range(n - 1, -1, -1):
7
            while stack and temperatures[stack[-1]] <= temperatures[i]:
8
                stack.pop()
9
            res[i] = 0 if not stack else stack[-1] - i
10
            stack.append(i)
11
        return res

LeetCode 496. 下一个更大元素 I#

题目链接

1
class Solution:
2
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
3
        greater = self.nextGreater(nums2)
4
        greater_map = {nums2[i]: greater[i] for i in range(len(nums2))}
5
        return [greater_map[num] for num in nums1]
6

7
    def nextGreater(self, nums):
8
        n = len(nums)
9
        res = [-1] * n
10
        s = []
11
        for i in range(n - 1, -1, -1):
12
            while s and s[-1] <= nums[i]:
13
                s.pop()
14
            res[i] = s[-1] if s else -1
15
            s.append(nums[i])
16
        return res

LeetCode 503. 下一个更大元素 II#

题目链接

1
class Solution:
2
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
3
        n = len(nums)
4
        res = [-1] * n
5
        s = []
6
        for i in range(2 * n - 1, -1, -1):  # 模拟数组的环形结构
7
            while s and s[-1] <= nums[i % n]:
8
                s.pop()
9
            res[i % n] = s[-1] if s else -1
10
            s.append(nums[i % n])
11
        return res