每日一题 2454. 下一个更大元素 IV（困难，单调栈）

1. 首先考虑第一大整数问题
2. 维护一个单调栈，遍历 nums，弹出栈中所有小于 nums[i] 的数，而 nums[i] 就是这些被弹出的数的第一大整数，知道栈为空或者栈顶元素比 nums[i] 大，证明如下，首先由于是遍历，所以 nums[i] 必定在栈中的元素之后，而如果 nums[i] 不是弹出的数的第一大整数（即在 i 之前还有比被弹出的数更大的整数），那么此时被弹出的数，应该在遍历到那个整数时就被弹出了
3. 对于题目要求的第二大整数的问题，只需要对栈中每个元素进行计数，只有当一个栈中元素第二次需要弹出时才弹出他，否则不弹出，但是同样的 nums[i] 需要插入至第一个比他大的栈中元素的顶上，以维护栈的单调性

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        d = {}
        d[0] = [-1, -2]
        d[-2] = [0, -2]
        d[-1] = [-1, 0]
        n = [0] * len(nums)
        ans = [-1] * len(nums)
        for i in range(1, len(nums)):
            k = d[-2][0]
            while nums[i] > nums[k]:
                n[k] += 1
                if n[k] == 2:
                    ans[k] = nums[i]
                    d[d[k][0]][1] = d[k][1]
                    d[d[k][1]][0] = d[k][0]
                k = d[k][0]
                if k == -1:
                    break
            
            d[i] = [k, d[k][1]]
            d[d[k][1]][0] = i
            d[k][1] = i
        
        return ans