力扣 2454. 下一个更大元素 IV

题目来源：https://leetcode.cn/problems/next-greater-element-iv/

大致题意：
给一个数组，求出每个位置之后大于当前元素的第二个元素值，如果没有则为 -1

比如数组 [1, 2, 4, 3]，索引 0 之后大于 1 的第二个元素值为 4，索引 1 之后大于 2 的第二个元素值为 3，剩下两个位置右侧没有满足要求的值

思路

使用单调栈可以求出大于当前位置的第一个元素值，那么如何求出第二个值呢

可以通过套娃单调栈来实现

首先使用维护一个非递增的单调栈，在遍历数组更新单调栈的过程中，如果当前元素大于单调栈栈顶元素，则表明当前元素是单调栈栈顶元素右侧的第一个更大元素。此时，弹出单调栈栈顶元素入辅助栈，也就是每次将单调栈弹出元素放入辅助栈。

那么，辅助栈中的元素都已经遇到了右侧第一个更大元素。于是可以在遍历数组时，判断辅助栈是否为空，在辅助栈不为空时，可以判断当前位置元素是否大于辅助栈中元素，若大于，则表明在辅助栈中的这些元素遇到了右侧第二个更大元素

具体实现时，因为辅助栈无需关注入栈顺序，更关注元素值的大小，所以使用优先队列更为合适

那么解题思路可以概括为：

1. 初始化单调栈和辅助队列，栈和队列存储的都是元素在数组中的索引。初始化答案数组元素都为 -1
2. 遍历数组
3. 当辅助队列不为空时，判断当前遍历元素与辅助队列最小值的关系，若当前元素大于辅助队列最小值，则队首元素出队，并更新对应索引的第二个更大元素。重复这个过程直至辅助队列为空或者当前遍历元素不大于辅助队列最小值
4. 当单调栈不为空，判断当前遍历元素是否大于栈顶元素，若大于则弹出栈顶元素入辅助队列，重复这个过程直至单调栈为空或者当前遍历元素小于等于栈顶元素
5. 将当前元素索引放入单调栈
6. 重复 2 - 5 步，直至遍历结束

代码：

public int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        // 单调栈
        Deque<Integer> firstStack = new ArrayDeque<>();
        // 辅助队列，队列元素按照数组中的值升序排序
        PriorityQueue<Integer> secondQueue = new PriorityQueue<>((a, b) -> nums[a] - nums[b]);
        // 初始化答案数组
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        // 遍历数组
        for (int i = 0; i < n; i++) {
            // 如果辅助队列不为空，且当前元素大于辅助队列最小值
            while (!secondQueue.isEmpty() && nums[secondQueue.peek()] < nums[i]) {
                ans[secondQueue.poll()] = nums[i];
            }
            // 如果单调栈不为空，且当前元素大于栈顶元素
            while (!firstStack.isEmpty() && nums[firstStack.peek()] < nums[i]) {
                secondQueue.offer(firstStack.pop());
            }
            // 将当前元素索引放入单调栈
            firstStack.push(i);
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24