题目：
给你一个下标从 0 开始的正整数数组 heights ，其中 heights[i] 表示第 i 栋建筑的高度。
如果一个人在建筑 i ，且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ，那么这个人可以移动到建筑 j 。
给你另外一个数组 queries ，其中 queries[i] = [ai, bi] 。第 i 个查询中，Alice 在建筑 ai ，Bob 在建筑 bi 。
请你能返回一个数组 ans ，其中 ans[i] 是第 i 个查询中，Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ，Alice 和 Bob 不能相遇，令 ans[i] 为 -1 。
示例 1：
输入：heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
输出：[2,5,-1,5,2]
解释：第一个查询中，Alice 和 Bob 可以移动到建筑 2 ，因为 heights[0] < heights[2] 且 heights[1] < heights[2] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[0] < heights[5] 且 heights[3] < heights[5] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Alice 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[3] < heights[5] 且 heights[4] < heights[5] 。
第五个查询中，Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。
示例 2：
输入：heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
输出：[7,6,-1,4,6]
解释：第一个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[0] < heights[7] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 6 ，因为 heights[3] < heights[6] 且 heights[5] < heights[6] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Bob 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 4 ，因为 heights[3] < heights[4] 且 heights[0] < heights[4] 。
第五个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[1] < heights[6] 。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。
提示：
1 <= heights.length <= 5 * 1041 <= heights[i] <= 1091 <= queries.length <= 5 * 104queries[i] = [ai, bi]0 <= ai, bi <= heights.length - 1
暴力判断
思路：
因为两个人都只能往右走，并且如果可以有共同的相遇地点，那么一步就可以走到。
所以我们需要记录 heights 数组的每一个索引，看他能到达哪些索引。记录一张领接表
对于每一个 query[i] 从判断 ai 和 bi 对应的领接表数组中，有没有相同元素，有就可以，没有就说明到达不了。
代码：
class Solution {
public:
vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
// 先统计每个从每个建筑出发，可以到达的建筑索引
// 然后对于每一个query，找到一个相同的索引就可以到达
int n = heights.size();
// 计算邻接表
vector<vector<int>> graph(n);
for (int i = 0; i < n; i++) {
graph[i].push_back(i);
for (int j = i + 1; j < n; j++) {
if (heights[j] > heights[i]) graph[i].push_back(j);
}
}
int m = queries.size();
vector<int> ans(m);
for (int i = 0; i < m; i++) {
int a = queries[i][0], b = queries[i][1];
int aIdx = 0, bIdx = 0, flag = 0;
while (aIdx < graph[a].size() && bIdx < graph[b].size()) {
if (graph[a][aIdx] == graph[b][bIdx]) {
ans[i] = graph[a][aIdx];
flag = 1;
break;
} else if (graph[a][aIdx] > graph[b][bIdx]) {
bIdx++;
} else {
aIdx++;
}
}
if (!flag) {
ans[i] = -1;
}
}
return ans;
}
};
离线 + 二分单调栈
思路：
由题意可知，人只能往右边移动，并且两人交换位置后不影响答案。对于每一次询问不妨设 ai < bi。如果 heights[ai] < heights[bi]，那么答案就是 bi，否则答案在 bi 右边。
令 hights 的长度为 n，问题转化为在区间 [bi + 1, n] 中找到最左边的下标 x 满足 heights[x] > heights[bi]，可以将查询离线处理，从后往前枚举，维护一个从大到小的单调栈 st。对于每一个 b，在单调栈中二分找到第一个大于 heights[a] 的即可。
代码：
class Solution {
public:
vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
int n = heights.size();
int m = queries.size();
vector<vector<pair<int, int>>> query(n);
vector<int> ans(m);
vector<int> st;
for (int i = 0; i < m; i++) {
int a = queries[i][0];
int b = queries[i][1];
if (a > b) swap(a, b);
if (a == b || heights[a] < heights[b]) {
ans[i] = b;
continue;
}
query[b].push_back(make_pair(i, heights[a]));
}
int top = -1;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < query[i].size(); j++) {
int q = query[i][j].first;
int val = query[i][j].second;
if (top == -1 || heights[st[0]] <= val) {
ans[q] = -1;
continue;
}
int l = 0, r = top;
while (l <= r) {
int mid = (l + r) >> 1;
if (heights[st[mid]] > val) {
l = mid + 1;
} else {
r = mid - 1;
}
}
ans[q] = st[r];
}
while (top >= 0 && heights[st[top]] <= heights[i]) {
st.pop_back();
top--;
}
st.push_back(i);
top++;
}
return ans;
}
};