2023-12-12每日一题
一、题目编号
2454. 下一个更大元素 IV
二、题目链接
点击跳转到题目位置
三、题目描述
给你一个下标从 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：
示例 2：
提示：
- 1 <= nums.length <= 105
- 0 <= nums[i] <= 109
四、解题代码
class Solution {
public:
vector<int> secondGreaterElement(vector<int>& nums) {
vector<int> res(nums.size(), -1);
stack<int> st;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
for (int i = 0; i < nums.size(); ++i) {
while (!q.empty() && q.top().first < nums[i]) {
res[q.top().second] = nums[i];
q.pop();
}
while (!st.empty() && nums[st.top()] < nums[i]) {
q.push({nums[st.top()], st.top()});
st.pop();
}
st.push(i);
}
return res;
}
};
五、解题思路
(1) 单调栈+优先队列。
