2454. 下一个更大元素 IV (opens new window)

1.单调栈+优先级队列

先考虑右侧第一个更大的元素问题如何解决?维护一个递减的单调栈，出栈元素的下一个更大元素即为当前元素。

对于本题，需要求出位于后两个位置的更大元素，因此上面思路中，出栈元素弹出后不能直接丢弃，而是存放到另一个单调栈(优先级队列)，当它再次被当前元素弹出栈时，当前元素即为该元素的“后二更大元素”。

• 栈一的单调性：由弹栈顺序来进行控制。
• 栈二的单调性：由于栈一弹出后直接进入栈二，因此用优先级队列控制。

class Solution {
    public int[] secondGreaterElement(int[] nums) {
        int[] res = new int[nums.length];
        Stack<int[]> stack1 = new Stack<>();
        PriorityQueue<int[]> stack2 = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        
        Arrays.fill(res,-1);
        for (int i = 0; i < nums.length; i++) {
            while (!stack2.isEmpty() && stack2.peek()[0] < nums[i]) {
                int[] pop = stack2.poll();
                res[pop[1]] = nums[i];
            }
            while (!stack1.isEmpty() && stack1.peek()[0] < nums[i]) {
                stack2.offer(stack1.pop());
            }
            stack1.push(new int[]{nums[i],i});
        }
        return res;
    }
}