leetcode：2454. 下一个更大元素 IV【sortedDict初探 + 双单调栈学习】

题目截图

题目分析

• 我们知道第一大元素直接用单调栈就可以了
• 那么第二大元素是不是把遇到过依次更大元素的入另一个栈，再碰到的话再成立呢？
• 双单调栈？
• 另一种想法是，从大往小遍历，保持序号顺序，保证前面加入的一定比当前的大；因此只需要考虑当前插入的位置后面的第k个，具体来说是j + k - 1的位置是存在的，那么这个数一定就是第k大的数

双单调栈解法

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        # 双单调栈
        # s存第一次，t存第二次
        s, t = [], [] # 递减栈
        ans = [-1] * len(nums)
        for i, x in enumerate(nums):
            # 第二个栈判断
            while t and nums[t[-1]] < x:
                ans[t.pop()] = x
            # 第一个栈判断
            j = len(s) - 1
            while j >= 0 and nums[s[j]] < x:
                j -= 1
            # 把第一个栈小于当前x的移到第二个栈
            t += s[j + 1:]
            del s[j + 1:]
            # 加入当前的x对应的i
            s.append(i)

        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

SortedDict解法

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        # 按从大到小排序
        a = [(x, i) for i, x in enumerate(nums)]
        a.sort(key = lambda it: (-it[0], it[1]))
        # sortedcontainers
        from sortedcontainers import SortedDict
        sd = SortedDict()
        k = 2
        ans = [-1] * len(a)
        for x, i in a:
            # 找到i对应的下标j
            j = sd.bisect_right(i)
            if j + k - 1 < len(sd):
                ans[i] = sd.peekitem(j + k - 1)[1]
            sd[i] = x # 存当前的值
        return ans


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结

• 单调栈on，sortedDict onlogn
• 解决一类问题：当前数后面的比它大的第k个数是多少？