Leetcode 2024-12-12 题目分享

2454. 下一个更大元素 IV [Hard] 题解

Leetcode 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：

输入：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 <= 10^5
0 <= nums[i] <= 10^9

思路

~~一眼感觉就是单调栈的题目，但还是无脑树状数组~~

首先看范围：1e9? ==> 离散化一下。
如果是求下一个更大的元素，那直接从后往前依次添加到树状数组；查询时取下标最小值即可（由于树状数组维护的是前缀信息，所以离散化时需要将大小翻转一下）。

[2,4,0,9,6] ==> mp[9:1, 6:2, 4:3, 2:4, 0:5]

查询0时，已有数组a：[0, 3, 4, 0, 0, 0] （3，4分别是数字9和6在nums的下标）。

0对应大小为5，所以比它大的肯定存储在数组a[1-4]位置上。

利用树状数组求出这个a[1-4]中维护的下标最小值，得到结果：nums[3] = 9。

如果是求第二大的元素，那其实与上面类似，仍然用树状数组维护，但查询时每次要维护两个比当前元素大的值，且他们在nums中下标最小。最后取两个中下标较大的为答案。

[2,4,0,9,6] ==> mp[9:1, 6:2, 4:3, 2:4, 0:5]

查询2时，已有数组a：[0, 3, 4, 1, 0, 2] （3，4，1，2分别是数字9，6，4，0在nums的下标）。

2对应大小为4，所以比它大的肯定存储在数组a[1-3]位置上。

则此时需要用树状数组维护a[1-3]中下标最小的和次小的：分别是1，3。

所以最终nums[3]=9是nums[0]=2的第二大的值。

但有一个问题：如果有两个相同的数字呢？树状数组同一个位置上要存储两个最小的下标

[2,4,4,6,4,4] ==> mp[6:1, 4:2, 2:3]

查询2时，已有数组a：[0, 3, {1,2,4,5}, 0] （3，{1,2,4,5}分别是数字6，4在nums的下标）。

2对应大小为3，所以比它大的肯定存储在数组a[1-2]位置上。

则此时需要用树状数组维护a[1-2]中下标中最小的和次小的。

即3 + {1,2,4,5} = {1,2,3,4,5} 中最小的和次小的

所以最终nums[2]=4是nums[0]=2的第二大的值。

可以发现对4维护的下标1，2，4，5中4和5都是无用的：因为如果一个数比4小，那么最后最终取最小和次小下标时，4和5是肯定不会选中的，所以每次只要维护两个最小值即可

代码

class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        // 离散化
        vector<int> tp = nums;
        sort(tp.begin(), tp.end());
        tp.erase(unique(tp.begin(), tp.end()), tp.end());
        unordered_map<int, int> mp;
        int n = nums.size(), m = tp.size();
        for (int i = 0;i < m;i++){
            mp[tp[i]] = m-i;  // 大小翻转
        }
        // 树状数组模版
        typedef pair<int, int> pii;
        vector<pii> tr(m+1, pii(1e9, 1e9));
        vector<int> ans(n, 0);
        function<void(int,int)> upd = [&](int dx, int val){
            for (int i = dx;i <= m;i += i&-i){
                // 因为nums下标是从后往前前遍历，后来的下标肯定比之前的小，所以直接更新即可。
                tr[i].second = tr[i].first;
                tr[i].first = val;
            }
        };
        function<int(int)> qry = [&](int dx){
            int x = 1e9, y = 1e9;
            for (int i = dx;i > 0;i -= i&-i){
                // 每次取当前位置两个下标最小值和已经得到的进行对比
                vector<int> cur = {x, y, tr[i].first, tr[i].second};
                sort(cur.begin(), cur.end());
                x = cur[0], y = cur[1];
            }
            return y == 1e9 ? -1 : nums[y];
        };
        for (int i = n-1;i >= 0;i--){
            ans[i] = qry(mp[nums[i]]-1);
            upd(mp[nums[i]], i);
        }      
        return ans;
    }
};

复杂度分析

时间：O(nlog n)。
空间：O(n)。