Hard

题目描述

给你一个下标从 0 开始的正整数数组 heights，其中 heights[i] 表示第 i 栋建筑的高度。

如果一个人在建筑 i，只有当 i < j 且 heights[i] < heights[j] 时，他们才能移动到任何其他建筑 j。

另给你一个数组 queries，其中 queries[i] = [ai, bi]。在第 i 个查询中，爱丽丝在建筑 ai，鲍勃在建筑 bi。

返回一个数组 ans，其中 ans[i] 是第 i 个查询中爱丽丝和鲍勃可以相遇的 最左边 建筑的下标。如果对于查询 i，爱丽丝和鲍勃不能移动到一个公共建筑，那么设置 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]
解释：
第 1 个查询，爱丽丝和鲍勃可以移动到建筑 2，因为 heights[0] < heights[2] 且 heights[1] < heights[2]。
第 2 个查询，爱丽丝和鲍勃可以移动到建筑 5，因为 heights[0] < heights[5] 且 heights[3] < heights[5]。
第 3 个查询，爱丽丝无法与鲍勃相遇，因为爱丽丝不能移动到任何其他建筑。
第 4 个查询，爱丽丝和鲍勃可以移动到建筑 5，因为 heights[3] < heights[5] 且 heights[4] < heights[5]。
第 5 个查询，爱丽丝和鲍勃已经在同一栋建筑中。

示例 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]

提示：

  • 1 <= heights.length <= 5 * 10^4
  • 1 <= heights[i] <= 10^9
  • 1 <= queries.length <= 5 * 10^4
  • queries[i] = [ai, bi]
  • 0 <= ai, bi <= heights.length - 1

解题思路

思路分析

这道题的核心是找到两个人能够相遇的最左侧建筑。我们需要理解移动规则：只能向右移动到更高的建筑。

基本情况处理：

  1. 如果两人在同一建筑（a == b），答案就是该建筑
  2. 如果 a < b 且 heights[a] < heights[b]，爱丽丝可以直接移动到鲍勃所在建筑，答案是 b
  3. 其他情况需要找到位置 > max(a,b) 且高度大于 max(heights[a], heights[b]) 的最左建筑

核心算法： 使用单调栈 + 二分查找的组合。主要思路是：

  1. 将查询按照右端点从大到小排序
  2. 维护一个从右向左的单调递减栈，存储可能的相遇建筑
  3. 对于每个查询，在栈中二分查找第一个高度足够的建筑

优化策略：

  • 单调栈确保我们总能找到最左侧的有效建筑
  • 二分查找将查询复杂度降低到 O(log n)
  • 离线处理查询避免重复计算

代码实现

class Solution {
public:
    vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
        int n = heights.size();
        int m = queries.size();
        
        // 存储查询和原始索引
        vector<pair<pair<int,int>, int>> sortedQueries;
        for (int i = 0; i < m; i++) {
            int a = queries[i][0], b = queries[i][1];
            if (a > b) swap(a, b);
            sortedQueries.push_back({{a, b}, i});
        }
        
        // 按照右端点从大到小排序
        sort(sortedQueries.begin(), sortedQueries.end(), 
             [](const auto& x, const auto& y) {
                 return x.first.second > y.first.second;
             });
        
        vector<int> result(m);
        vector<pair<int, int>> stack; // {height, index}
        int j = n - 1;
        
        for (auto& query : sortedQueries) {
            int a = query.first.first, b = query.first.second;
            int queryIdx = query.second;
            
            // 处理简单情况
            if (a == b) {
                result[queryIdx] = a;
                continue;
            }
            if (heights[a] < heights[b]) {
                result[queryIdx] = b;
                continue;
            }
            
            // 将位置 > b 的建筑加入栈
            while (j > b) {
                while (!stack.empty() && stack.back().first <= heights[j]) {
                    stack.pop_back();
                }
                stack.push_back({heights[j], j});
                j--;
            }
            
            // 二分查找第一个高度 > heights[a] 的建筑
            int left = 0, right = stack.size() - 1;
            int ans = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (stack[mid].first > heights[a]) {
                    ans = stack[mid].second;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            result[queryIdx] = ans;
        }
        
        return result;
    }
};

class Solution:
    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
        n = len(heights)
        m = len(queries)
        
        # 存储查询和原始索引
        sorted_queries = []
        for i in range(m):
            a, b = queries[i]
            if a > b:
                a, b = b, a
            sorted_queries.append(((a, b), i))
        
        # 按照右端点从大到小排序
        sorted_queries.sort(key=lambda x: x[0][1], reverse=True)
        
        result = [0] * m
        stack = []  # (height, index)
        j = n - 1
        
        for (a, b), query_idx in sorted_queries:
            # 处理简单情况
            if a == b:
                result[query_idx] = a
                continue
            if heights[a] < heights[b]:
                result[query_idx] = b
                continue
            
            # 将位置 > b 的建筑加入栈
            while j > b:
                while stack and stack[-1][0] <= heights[j]:
                    stack.pop()
                stack.append((heights[j], j))
                j -= 1
            
            # 二分查找第一个高度 > heights[a] 的建筑
            left, right = 0, len(stack) - 1
            ans = -1
            while left <= right:
                mid = (left + right) // 2
                if stack[mid][0] > heights[a]:
                    ans = stack[mid][1]
                    right = mid - 1
                else:
                    left = mid + 1
            result[query_idx] = ans
        
        return result

public class Solution {
    public int[] LeftmostBuildingQueries(int[] heights, int[][] queries) {
        int n = heights.Length;
        int m = queries.Length;
        
        // 存储查询和原始索引
        var sortedQueries = new List<((int a, int b), int idx)>();
        for (int i = 0; i < m; i++) {
            int a = queries[i][0], b = queries[i][1];
            if (a > b) (a, b) = (b, a);
            sortedQueries.Add(((a, b), i));
        }
        
        // 按照右端点从大到小排序
        sortedQueries.Sort((x, y) => y.Item1.b.CompareTo(x.Item1.b));
        
        var result = new int[m];
        var stack = new List<(int height, int index)>();
        int j = n - 1;
        
        foreach (var query in sortedQueries) {
            int a = query.Item1.a, b = query.Item1.b;
            int queryIdx = query.idx;
            
            // 处理简单情况
            if (a == b) {
                result[queryIdx] = a;
                continue;
            }
            if (heights[a] < heights[b]) {
                result[queryIdx] = b;
                continue;
            }
            
            // 将位置 > b 的建筑加入栈
            while (j > b) {
                while (stack.Count > 0 && stack[stack.Count - 1].height <= heights[j]) {
                    stack.RemoveAt(stack.Count - 1);
                }
                stack.Add((heights[j], j));
                j--;
            }
            
            // 二分查找第一个高度 > heights[a] 的建筑
            int left = 0, right = stack.Count - 1;
            int ans = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (stack[mid].height > heights[a]) {
                    ans = stack[mid].index;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            result[queryIdx] = ans;
        }
        
        return result;
    }
}

var leftmostBuildingQueries = function(heights, queries) {
    const n = heights.length;
    const result = new Array(queries.length).fill(-1);
    const pending = [];
    
    for (let i = 0; i < n; i++) {
        pending.push([]);
    }
    
    for (let i = 0; i < queries.length; i++) {
        let [a, b] = queries[i];
        if (a > b) [a, b] = [b, a];
        
        if (a === b) {
            result[i] = a;
        } else if (heights[a] < heights[b]) {
            result[i] = b;
        } else {
            pending[b].push([Math.max(heights[a], heights[b]), i]);
        }
    }
    
    const minHeap = [];
    
    for (let i = 0; i < n; i++) {
        for (const [minHeight, queryIdx] of pending[i]) {
            minHeap.push([minHeight, queryIdx]);
        }
        
        while (minHeap.length > 0 && minHeap[0][0] < heights[i]) {
            const [_, queryIdx] = minHeap.shift();
            result[queryIdx] = i;
            minHeap.sort((a, b) => a[0] - b[0]);
        }
        
        minHeap.sort((a, b) => a[0] - b[0]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O((n + m) log n)排序查询 O(m log m)，处理查询 O(m log n)，维护单调栈 O(n)
空间复杂度O(n + m)单调栈空间 O(n)，查询排序空间 O(m)

相关题目