题目描述
leetcode 困难题
给你一个下标从 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] 。
|
提示1：
1
2
| 1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
|
单调栈+优先队列
先考虑找 $nums[i]$ 的第一大元素，显然我们可以通过单调栈求出，那么此时在第一大元素后面第一个大于 $nums[i]$ 的数即为第二大元素。
具体来说，顺序遍历数组，维护一个栈顶到栈底单调递增的单调栈，对于每个 $nums[i]$ ，如果大于栈顶元素，则当前元素为栈顶元素的第一大元素，弹出该栈顶，此时显然右边第一个大于栈顶的元素为栈顶的第二大元素。那么类似找第一个元素的过程，我们可以第二个单调栈保存所弹出的元素，后续遍历过程中只要某个元素 $nums[i]$ 大于第二个单调栈的栈顶，说明 $nums[i]$ 为第二个单调栈的栈顶的第二大元素。
需要注意的是，类似第一个单调栈，第二个单调栈也需要维护栈顶到栈底单调递增的性质，一种方法是在对第一个栈做弹出时，使用一个临时栈来保存所弹出顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int[] secondGreaterElement(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
Deque<Integer> monoStack = new ArrayDeque<>();
Deque<Integer> secondMonoStack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while(!secondMonoStack.isEmpty() && nums[secondMonoStack.peek()] < nums[i]){
ans[secondMonoStack.pop()] = nums[i];
}
Deque<Integer> temp = new ArrayDeque<>();
while (!monoStack.isEmpty() && nums[monoStack.peek()] < nums[i]) {
temp.push(monoStack.pop());
}
monoStack.push(i);
while(!temp.isEmpty()){
secondMonoStack.push(temp.pop());
}
}
return ans;
}
}
|
也可以直接用优先队列来省去一些代码，但对应时间复杂度会多一个 $log$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int[] secondGreaterElement(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
Deque<Integer> monoStack = new ArrayDeque<>();
PriorityQueue<Integer> secondHigherQueue = new PriorityQueue<>((a, b) -> nums[a] - nums[b]);
for (int i = 0; i < n; i++) {
while(!secondHigherQueue.isEmpty() && nums[secondHigherQueue.peek()] < nums[i]){
ans[secondHigherQueue.poll()] = nums[i];
}
while (!monoStack.isEmpty() && nums[monoStack.peek()] < nums[i]) {
secondHigherQueue.offer(monoStack.pop());
}
monoStack.push(i);
}
return ans;
}
}
|