一、$leetcode.2454$-下一个更大的元素(右边第二大)

1. 分析

暴力的做法是对于每个$i$，从左往右扫到右端点来维护第二大的元素的下标，时间复杂度$O(n^2)$。很容易想到我们需要找一个扫一遍并用某种数据结构存下已经扫过的信息的做法。
我们将下标按照数值排序，然后从右往左扫，$i$右边的数一定是比当前数大的，我们只需要将右侧所有数在原数组中的下标存下来，排序后二分出比当前数下标大的第二个下标即可。我们可以在从右往左扫的同时用$set$来存右边所有点的下标，插入的同时也完成了排序$(O(logn))$

2. 注意要将相同值的数一次性处理

因为对于$x$这个数，它右侧的数一定要都比它大，如果有相同的数，会影响到二分第二个比它大的下标的答案

class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& w) {
        int n = w.size();
        vector<int> p(n);
        for (int i = 0; i < n; i ++) p[i] = i;  // 下标赋初值
        sort(p.begin(), p.end(), [&](int x, int y) {  // 将下标按照数值排序
            return w[x] > w[y];
        });
        set<int> st;
        st.insert(n + 1), st.insert(n + 2);  // 先插入两个更大的数值，避免二分找不到
        vector<int> res(n, -1);  // 存答案
        for (int i = 0; i < n; i ++)
        {
            int j = i + 1;
            while (j < n && w[p[j]] == w[p[i]]) j ++;  // w[i]一样的数一次性处理
            for (int k = i; k < j; k ++)
            {
                auto it = st.upper_bound(p[k]);
                ++ it;
                if (*it < n) res[p[k]] = w[*it];
            }
            for (int k = i; k < j; k ++) st.insert(p[k]);
            i = j - 1;
        }
        return res;
    }
};

二、右边第$k$大

同上面的思路，我们只需要二分出第一个比$x$下标大的下标，再加上$k-1$即可，同理我们也可以处理左侧