leetcode线段树(2940. 找到 Alice 和 Bob 可以相遇的建筑)
前言
经过前期的基础训练以及部分实战练习，粗略掌握了各种题型的解题思路。现阶段开始专项练习。
描述
给你一个下标从 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
实现原理与步骤
1.题目意思解析
queries[i][0]和queries[i][1]相等情况下返回queryies[i][0];
queries[i][0]和queries[i][1]不等情况下，找到最接近的下标j使得height(j)>Math.max(height(queries[i][0]),height(queries[i][1])).
2.本题模拟算法情况下会超时，当存在大量queries情况下线段树方法是合理的选择。
3.线段树的构建没什么特殊，特殊的是查询条件变了。
原本查询的区间条件left和right变为起点查询条件pos和Math.max(height(queries[i][0]),height(queries[i][1])的val值。
- 当Math.max(height(queries[i][0]),height(queries[i][1]))大于zd[node]时跳过当前node对应的线段，返回0.
- 当pos<=mid时跳过该线段查询，由于递归的下标从小到大，所以跳过该段查询后下一段最小的序号即为对应最接近的下标j。
- 当start==end时返回节点的序号start，也就是找到最接近的下标j使得height(j)>Math.max(height(queries[i][0]),height(queries[i][1]))
实现代码
class Solution {int[] zd;public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {int n = heights.length;zd = new int[n * 4];buildTree(heights,0, 0, n-1);int m = queries.length;int[] ans = new int[m];for (int i = 0; i < m; i++) {int a = queries[i][0];int b = queries[i][1];if (a > b) {int temp = a;a = b;b = temp;}if (a == b || heights[a] < heights[b]) {ans[i] = b;continue;}int tempRes = queryTree(0,0,n-1,b + 1, heights[a]);ans[i]=tempRes==0?-1:tempRes;}return ans;}public void buildTree(int[] nums, int node, int start, int end) {if (start == end) {zd[node] = nums[start];} else {int mid = (start + end) / 2;int leftChild = 2 * node + 1;int rightChild = 2 * node + 2;buildTree(nums, leftChild, start, mid);buildTree(nums, rightChild, mid + 1, end);zd[node] = Math.max(zd[leftChild] ,zd[rightChild]);}}private int queryTree(int node, int start, int end, int pos, int val) {if (val>=zd[node]) {return 0;}if (start==end) {return start;}int mid = (start + end) / 2;int leftChild = 2 * node + 1;int rightChild = 2 * node + 2;if(pos<=mid){int res = queryTree(leftChild, start, mid, pos, val);if(res!=0){return res;}}return queryTree(rightChild, mid + 1, end, pos, val);}
}