LeetCode 6227. 下一个更大元素 IV

LeetCode 6227. 下一个更大元素 IV

名次树

class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        sort(p.begin(), p.end(), [&](int a, int b){
            return nums[a] > nums[b];
        });

        set<int> S;
        S.insert(n + 1), S.insert(n + 2);
        vector<int> res(n, -1);
        for(int i = 0; i < n; i ++)
        {
            int j = i + 1;
            while(j < n && nums[p[i]] == nums[p[j]]) j ++;

            for(int k = i; k < j; k ++)
            {
                auto it = S.upper_bound(p[k]);
                it ++;
                if(*it < n)
                    res[p[k]] = nums[* it];
            }
            for(int k = i; k < j; k ++)
                S.insert(p[k]);
            i = j - 1;
        }
        return res;
    }
};

单调栈