找到Alice和Bob可以相遇的建筑(单调栈+二分)

原题链接

题意： 给定长度为n的数组表示建筑高度,定义i<j&&height[i]<height[j]则i可到达j;给出q组询问[a,b]，问a和b能到达的第一个建筑，没有则返回-1;
思路：
先对q组询问按两个中较大的数字从大到小排序，然后从后往前枚举数组height，维护一个单调递减栈，若当前下标i有相应的一组询问，则取出与i对应的另一个下标j，然后在单调栈中二分最近的下标k使得height[k]>height[j],此时该询问对应的答案即为k

class Solution {
private:
    int solve(const vector<int> &st, const vector<int>& heights, int v) {
        if (v >= heights[st[0]])
            return -1;

        int l = 0, r = st.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (v < heights[st[mid + 1]]) l = mid + 1;
            else r = mid;
        }

        return st[l];
    }

public:
    vector<int> leftmostBuildingQueries(vector<int>& heights,
        vector<vector<int>>& queries
    ) {
        const int n = heights.size(), m = queries.size();

        vector<int> qid(m);
        for (int i = 0; i < m; i++) {
            if (queries[i][0] > queries[i][1])
                swap(queries[i][0], queries[i][1]);

            qid[i] = i;
        }

        sort(qid.begin(), qid.end(), [&](int x, int y) {
            return queries[x][1] > queries[y][1];
        });

        vector<int> st, ans(m);
        for (int i = n - 1, j = 0; i >= 0; i--) {
            while (!st.empty() && heights[i] > heights[st.back()])
                st.pop_back();

            st.push_back(i);

            while (j < m && queries[qid[j]][1] == i) {
                int x = queries[qid[j]][0], y = queries[qid[j]][1];
                if (x == y || heights[x] < heights[y])
                    ans[qid[j]] = y;
                else
                    ans[qid[j]] = solve(st, heights, heights[x]);
                ++j;
            }
        }

        return ans;
    }
};