给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。
如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：
j > inums[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：
输入：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：
输入：nums = [3,3] 输出：[-1,-1] 解释： 由于每个数右边都没有更大的数，所以我们返回 [-1,-1] 。
提示：
1 <= nums.length <= 1050 <= nums[i] <= 109
方法一：单调栈 + 优先队列（小根堆）
求下一个更大的元素，可以使用单调栈来实现。我们维护一个栈，然后从左到右遍历数组，如果栈顶元素小于当前元素，则当前元素就是栈顶元素的下一个更大的元素。
这道题的变形是求下一个更大的元素的下一个更大的元素，即第二大的元素。我们观察单调栈求下一个更大元素的过程，每次出栈时，栈顶元素找到了下一个更大的元素，但我们是要为栈顶元素找到第二个更大的元素。次数，我们可以将栈顶元素出栈，放到一个优先队列（小根堆）中。每次遍历数组元素时，先判断当前元素是否大于优先队列的堆顶元素，如果大于，说明堆顶元素找打了第二个更大的元素，更新答案数组，然后弹出堆顶元素，继续判断当前元素是否大于优先队列的堆顶元素，直到堆为空或者当前元素不大于堆顶元素。
接着，执行单调栈的相关操作，弹出栈顶元素后，放入到优先队列中。
时间复杂度
class Solution:
def secondGreaterElement(self, nums: List[int]) -> List[int]:
stk = []
q = []
ans = [-1] * len(nums)
for i, v in enumerate(nums):
while q and q[0][0] < v:
ans[q[0][1]] = v
heappop(q)
while stk and nums[stk[-1]] < v:
heappush(q, (nums[stk[-1]], stk.pop()))
stk.append(i)
return ansclass Solution {
public int[] secondGreaterElement(int[] nums) {
Deque<Integer> stk = new ArrayDeque<>();
PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]);
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
for (int i = 0; i < n; ++i) {
int v = nums[i];
while (!q.isEmpty() && q.peek()[0] < v) {
ans[q.peek()[1]] = v;
q.poll();
}
while (!stk.isEmpty() && nums[stk.peek()] < v) {
q.offer(new int[] {nums[stk.peek()], stk.pop()});
}
stk.push(i);
}
return ans;
}
}using pii = pair<int, int>;
class Solution {
public:
vector<int> secondGreaterElement(vector<int>& nums) {
stack<int> stk;
priority_queue<pii, vector<pii>, greater<pii>> q;
int n = nums.size();
vector<int> ans(n, -1);
for (int i = 0; i < n; ++i) {
int v = nums[i];
while (!q.empty() && q.top().first < v) {
ans[q.top().second] = v;
q.pop();
}
while (!stk.empty() && nums[stk.top()] < v) {
q.push({nums[stk.top()], stk.top()});
stk.pop();
}
stk.push(i);
}
return ans;
}
};func secondGreaterElement(nums []int) []int {
stk := []int{}
q := hp{}
n := len(nums)
ans := make([]int, n)
for i := range ans {
ans[i] = -1
}
for i, v := range nums {
for len(q) > 0 && q[0].v < v {
ans[q[0].i] = v
heap.Pop(&q)
}
for len(stk) > 0 && nums[stk[len(stk)-1]] < v {
heap.Push(&q, pair{nums[stk[len(stk)-1]], stk[len(stk)-1]})
stk = stk[:len(stk)-1]
}
stk = append(stk, i)
}
return ans
}
type pair struct{ v, i int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool {
a, b := h[i], h[j]
return a.v < b.v
}
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }