DeepSeek LeetCode 2940. 找到 Alice 和 Bob 可以相遇的建筑 Java实现

以下是 LeetCode 2940「找到 Alice 和 Bob 可以相遇的建筑」的 Java 实现使用线段树 二分查找的思路javaclass Solution {private int[] heights;private int[] segTree;private int n;public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {this.heights heights;this.n heights.length;this.segTree new int[4 * n];build(1, 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) {ans[i] a;continue;}int left Math.min(a, b);int right Math.max(a, b);// 若左侧建筑高度 右侧建筑高度则右侧建筑即为答案if (heights[left] heights[right]) {ans[i] right;continue;}// 需要在右侧寻找第一个高度 max(heights[left], heights[right]) 的建筑int target Math.max(heights[left], heights[right]);int pos queryFirst(1, 0, n - 1, right, target);ans[i] pos;}return ans;}// 构建线段树存储区间最大值private void build(int node, int l, int r) {if (l r) {segTree[node] heights[l];return;}int mid (l r) / 2;build(node * 2, l, mid);build(node * 2 1, mid 1, r);segTree[node] Math.max(segTree[node * 2], segTree[node * 2 1]);}// 查询区间 [l, r] 中第一个下标 start 且高度 target 的位置private int queryFirst(int node, int l, int r, int start, int target) {// 当前区间完全在 start 左侧或区间最大值 target无解if (r start || segTree[node] target) {return -1;}if (l r) {return l;}int mid (l r) / 2;// 优先在左子树查找int leftRes queryFirst(node * 2, l, mid, start, target);if (leftRes ! -1) {return leftRes;}// 左子树无结果再查右子树return queryFirst(node * 2 1, mid 1, r, start, target);}}算法核心1. 问题简化· 设 left min(a, b)right max(a, b)。· 若 left right答案即为 left。· 若 heights[left] heights[right]则 right 可直接作为答案。· 否则需要找到下标 ≥ right 且高度 max(heights[left], heights[right]) 的最左建筑。2. 线段树· 维护区间最大值用于快速判断某个区间是否存在高度大于目标值的建筑。· 通过递归二分查找定位第一个满足条件的位置。3. 复杂度· 构建线段树O(n)· 每个查询O(log n)· 总时间复杂度O((n q) log n)空间 O(n)该方法充分利用了线段树的区间查询能力简洁高效。