单调栈的相关应用

相关题目：
496. 下一个更大元素 I
503. 下一个更大元素 II
739. 每日温度

class NextGreaterElement:
    """
    496. 下一个更大元素 I
    https://leetcode.cn/problems/next-greater-element-i/
    """
    def solution(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 记录 nums2 中每个元素的下一个更大元素
        greater = self.nextGreater(nums2)
        # 转化成映射：元素 x -> x 的下一个最大元素
        greaterMap = {}
        for i in range(len(nums2)):
            greaterMap[nums2[i]] = greater[i]
        # nums1 是 nums2 的子集，所以根据 greaterMap 可以得到结果
        res = []
        for num in nums1:
            res.append(greaterMap[num])
        return res

    # 计算 nums 中每个元素的下一个更大元素
    def nextGreater(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [-1]*n
        # 自底向上的单调栈，单调递减
        stk = []
        for i in range(n-1, -1, -1):
            while stk and stk[-1] <= nums[i]:
                stk.pop()

            if stk:
                res[i] = stk[-1]

            stk.append(nums[i])

        return res


class NextGreaterElements:
    """
    针对环形数组的处理，常用套路就是将数组长度翻倍
    503. 下一个更大元素 II
    https://leetcode.cn/problems/next-greater-element-ii/description/
    """
    def solution(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [-1]*n
        # 自底向上的单调栈，单调递减
        stk = []
        for i in range(2*n-1, -1, -1):
            while stk and stk[-1] <= nums[i%n]:
                stk.pop()

            if stk:
                res[i%n] = stk[-1]

            stk.append(nums[i%n])

        return res


class DailyTemperatures:
    """
    739. 每日温度
    https://leetcode.cn/problems/daily-temperatures/
    """
    def solution(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        res = [0]*n
        # 自底向上的单调栈，单调递减
        stk = []
        for i in range(n-1, -1, -1):
            while stk and temperatures[stk[-1]] <= temperatures[i]:
                stk.pop()

            if stk:
                res[i] = stk[-1]-i

            stk.append(i)

        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80