2454. 下一个更大元素 IV(2175)

给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。

如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：

  • j > i
  • nums[j] > nums[i]
  • 恰好存在 一个 k 满足 i < k < j 且 nums[k] > nums[i] 。

如果不存在 nums[j] ，那么第二大整数为 -1 。

  • 比方说，数组 [1, 2, 4, 3] 中，1 的第二大整数是 4 ，2 的第二大整数是 3 ，3 和 4 的第二大整数是 -1 。

请你返回一个整数数组 answer ，其中 answer[i]是 nums[i] 的第二大整数。

示例 1：

1
2
3
4
5
6
7
8
9
输入：nums = [2,4,0,9,6]
输出：[9,6,6,-1,-1]
解释：
下标为 0 处：2 的右边，4 是大于 2 的第一个整数，9 是第二个大于 2 的整数。
下标为 1 处：4 的右边，9 是大于 4 的第一个整数，6 是第二个大于 4 的整数。
下标为 2 处：0 的右边，9 是大于 0 的第一个整数，6 是第二个大于 0 的整数。
下标为 3 处：右边不存在大于 9 的整数，所以第二大整数为 -1 。
下标为 4 处：右边不存在大于 6 的整数，所以第二大整数为 -1 。
所以我们返回 [9,6,6,-1,-1] 。

示例 2：

1
2
3
4
输入：nums = [3,3]
输出：[-1,-1]
解释：
由于每个数右边都没有更大的数，所以我们返回 [-1,-1] 。

提示：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
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
/**
idx num stack   second  res
0 2 [2]  []     [−1,−1,−1,−1,−1]
1 4 [4]  [2]  [−1,−1,−1,−1,−1]
2 0 [4,0]   [2]     [−1,−1,−1,−1,−1]
3 9 [9]  [4,0] [9,−1,−1,−1,−1]
4 6 [9,6]   []     [9,6,6,−1,−1]
 */
class Solution {
    public int[] secondGreaterElement(int[] nums) {
        int n = nums.length, res[] = new int[n];
        Arrays.fill(res, -1);
        // 第一个递减栈，和计算第一个更大值用的递减栈一样
        Deque<Integer> stack = new LinkedList<>();
        // 第二个递减栈
        Deque<Integer> secondStack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            while (!secondStack.isEmpty() && nums[i] > nums[secondStack.peek()]) {  // 从第二个递减栈得到答案
                res[secondStack.pop()] = nums[i];
            }
            // 第一个递减栈弹出的顺序是递增的，所以push到第二个递减栈之前需要用一个临时的栈反转一下
            Deque<Integer> temp = new LinkedList<>();
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) temp.push(stack.pop());
            while (!temp.isEmpty()) secondStack.push(temp.pop());
            stack.push(i);
        }
        return res;
    }
}