【每日一题】下一个更大元素 IV

Tag

【单调栈】【2023-12-12】

---

题目来源

2454. 下一个更大元素 IV

---

题目解读

在数组中找出当前元素右侧第二个比自己大的整数，如果不存在，那么第二个比自己大的整数为 -1。

---

解题思路

方法一：单调栈+优先队列

思路

在介绍方法一之前需要先了解如何使用「单调栈」来求解 496. 下一个更大元素 I。简单说一下思路：遍历数组，如果数组当前元素大于栈顶元素，那么栈顶元素就找到了下一个更大的元素。根据该思想，可以在 $O(n)$ 时间内解决下一个更大元素问题。

本题中，依旧使用该思想先找到某个元素的「第一个更大元素」。然后，将已经找到「第一个更大元素」的元素存入优先队列 pq 中。

具体操作如下：

• 若 pq 非空且堆顶元素小于当前遍历的元素时，说明当前元素为堆顶元素的「第二大」的整数，我们取出堆顶元素，并更新结果数组。重复该操作直至 qqq 为空或者堆顶元素大于等于当前遍历元素；
• 若 st 非空且栈顶元素对应的值小于当前遍历元素，则说明找到了栈顶元素的下一个更大的数字，将栈顶元素出栈，并加入堆 pq 中。重复执行该操作直至 st 为空或者栈顶元素大于等于当前遍历元素；
• 将当前元素的下标压入栈 st 中。

算法

class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        stack<int> st;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (int i = 0; i < n; ++i) {
            while (!pq.empty() && pq.top().first < nums[i]) {
                res[pq.top().second] = nums[i];
                pq.pop();
            }
            while (!st.empty() && nums[st.top()] < nums[i]) {
                pq.push({nums[st.top()], st.top()});
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
};

复杂度分析

时间复杂度：$O(nlogn)$，$n$ 为数组 nums 的大小。每个元素最多出入一次优先队列。

空间复杂度：$O(n)$。

---

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。