What is the main pattern to solve Find Building Where Alice and Bob Can Meet?

The key pattern is binary search over the valid answer space combined with monotonic stack precomputation for next taller buildings.

Can Alice and Bob meet at their starting buildings?

Yes, if both start at the same building, that counts as a valid meeting building.

Why do we need to swap ai and bi when ai > bi?

Swapping ensures the binary search moves in the correct direction, maintaining the i < j constraint for valid movements.

What if no building exists where both can meet?

Return -1 for that query, indicating no valid meeting building is reachable from both starting points.

How does monotonic stack help in this problem?

It precomputes the next taller building for each index, allowing quick validation during binary search and avoiding repeated linear scans.

#2940

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

找到 Alice 和 Bob 可以相遇的建筑

给你一个下标从 0 开始的正整数数组 heights ，其中 heights[i] 表示第 i 栋建筑的高度。如果一个人在建筑 i ，且存在 i 的建筑 j 满足 heights[i] ，那么这个人可以移动到建筑 j 。给你另外一个数组 queries ，其中 queries[i] = [a i…

数组二分查找栈树状数组线段树

题目描述

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

如果一个人在建筑 i ，且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ，那么这个人可以移动到建筑 j 。

给你另外一个数组 queries ，其中 queries[i] = [a_i, b_i] 。第 i 个查询中，Alice 在建筑 a_i ，Bob 在建筑 b_i。

请你能返回一个数组 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 * 10⁴
1 <= heights[i] <= 10⁹
1 <= queries.length <= 5 * 10⁴
queries[i] = [a_i, b_i]
0 <= a_i, b_i <= heights.length - 1

lightbulb

解题思路

方法一：树状数组

我们不妨记 $queries[i] = [l_i, r_i]$ ，其中 $l_i \le r_i$ 。如果 $l_i = r_i$ 或者 $heights[l_i] \lt heights[r_i]$ ，那么答案就是 $r_i$ 。否则，我们需要在所有满足 $j \gt r_i$ ，且 $heights[j] \gt heights[l_i]$ 的 $j$ 中找到最小的 $j$ 。

我们可以将 $queries$ 按照 $r_i$ 从大到小排序，用一个指针 $j$ 指向当前遍历到的 $heights$ 的下标。

接下来，我们遍历每个查询 $queries[i] = (l, r)$ ，对于当前查询，如果 $j \gt r$ ，那么我们循环将 $heights[j]$ 插入树状数组中。树状数组维护的是后缀高度（离散化后的高度）的下标的最小值。然后，我们判断是否满足 $l = r$ 或者 $heights[l] \lt heights[r]$ ，如果满足，那么当前查询的答案就是 $r$ ，否则，我们在树状数组中查询 $heights[l]$ 的下标的最小值，即为当前查询的答案。

时间复杂度 $O((n + m) \times \log n + m \times \log m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别为 $heights$ 和 $queries$ 的长度。

相似题目：

2736. 最大和查询

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

class BinaryIndexedTree:
    __slots__ = ["n", "c"]

    def __init__(self, n: int):
        self.n = n
        self.c = [inf] * (n + 1)

    def update(self, x: int, v: int):
        while x <= self.n:
            self.c[x] = min(self.c[x], v)
            x += x & -x

    def query(self, x: int) -> int:
        mi = inf
        while x:
            mi = min(mi, self.c[x])
            x -= x & -x
        return -1 if mi == inf else mi


class Solution:
    def leftmostBuildingQueries(
        self, heights: List[int], queries: List[List[int]]
    ) -> List[int]:
        n, m = len(heights), len(queries)
        for i in range(m):
            queries[i] = [min(queries[i]), max(queries[i])]
        j = n - 1
        s = sorted(set(heights))
        ans = [-1] * m
        tree = BinaryIndexedTree(n)
        for i in sorted(range(m), key=lambda i: -queries[i][1]):
            l, r = queries[i]
            while j > r:
                k = n - bisect_left(s, heights[j]) + 1
                tree.update(k, j)
                j -= 1
            if l == r or heights[l] < heights[r]:
                ans[i] = r
            else:
                k = n - bisect_left(s, heights[l])
                ans[i] = tree.query(k)
        return ans

speed

复杂度分析

指标	值
时间	O(q \cdot \log q + n)
空间	O(n + q)

psychology

面试官常问的追问

外企场景

question_mark
They may ask about optimizing repeated query checks using precomputation.
question_mark
Expect clarification questions on why binary search works over the answer space, not the array directly.
question_mark
They may probe how to handle queries where Alice and Bob start at the same building.

warning

常见陷阱

外企场景

error
Failing to swap query indices when ai > bi, leading to invalid search ranges.
error
Overlooking that the meeting building must be taller than both starting buildings.
error
Using linear search per query instead of binary search, causing timeouts for large inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow movements to buildings with equal height instead of strictly taller.
arrow_right_alt
Return all possible meeting buildings instead of just the leftmost one.
arrow_right_alt
Consider bidirectional movement where i > j is also allowed if heights[i] < heights[j].

help

常见问题

外企场景

继续练习

#2736 最大和查询 #2454 下一个更大元素 IV #2945 找到最大非递减数组的长度