Leetcode 2940. Find Building Where Alice and Bob Can Meet

• Leetcode 2940. Find Building Where Alice and Bob Can Meet
  • 1. 解题思路
  • 2. 代码实现
  • 3. 算法优化

• 题目链接：2940. Find Building Where Alice and Bob Can Meet

1. 解题思路

这一题本质上又是限制条件下求极值的问题，算是我最不喜欢的题目类型之一吧，因为真的挺考验智商的……

很不幸，没想到啥好的思路，还是分步实现的策略，第一步就是找到每一个位置上后续能够访问的全部位置，然后第二步就是在对于query的两个位置直接获得他们能够访问的位置，然后求公共的最小元素。

显然，对于第一个问题，我们只需要对原数组进行排序，然后从高到低依次插入到有序队列当中，此时其插入时队列后方的所有元素就为其能够访问的所有位置。

由此，我们就能够在$O(N\cdot logN)$的时间复杂度能找到所有坐标上能够访问的所有位置。然后，剩下的问题就是如何去找到两个有序数列的最小公共元素。

这里，我做了个小trick，就是注意到了对于上述问题，显然如果两个序列有交集，那么显然，对于其中起始位置更高的那个序列（不妨记作序列A）而言，其最后一个元素必然也在另一个序列（不妨记作序列B）当中，且满足从某一个位置开始，必然有后方元素全在序列B当中，而其前方的序列均不在序列A当中。

由此，我们就可以使用一个二分搜索来快速找寻上述最小公共坐标了，所有query的时间复杂度也为$O(N\cdot logN)$。

然而没有想到的是，这里居然遇到了内存爆炸的问题，就很懵逼……

这里，我是通过剪枝和及时删除的方法处理掉了这个问题，但是这里多少有点取巧了，而且非常的不优雅，就很难受了。

所谓剪枝倒是思路还挺自然，因为如果有两个坐标$i,j$，满足$i=j$或者$i<j$且$h_i<h_j$，那答案就是$j$，反之亦然。这样，我们就可以先去掉很多easy case了。

然后，关于及时删除，就是首先对query也进行一下排序，然后优先做那些可以快速得到后方位置的坐标对应的query，然后在他们后续不会再被使用时及时进行删除，通过这种方式，我们在这道题上面是通过了测试样例，不过很取巧就是了……

2. 代码实现

给出python代码实现如下：

class Solution:def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:buildings = [(idx, h) for idx, h in enumerate(heights)]buildings = sorted(buildings, key=lambda x: (x[1], -x[0]), reverse=True)indexes = {x[0]: i for i, x in enumerate(buildings)}res = [-1 for _ in queries]queries = [(idx, i, j) for idx, (i, j) in enumerate(queries)]for idx, i, j in queries:if i == j:res[idx] = ielif i < j and heights[i] < heights[j]:res[idx] = jelif i > j and heights[i] > heights[j]:res[idx] = iqueries = [(idx, i, j) if indexes[i] < indexes[j] else (idx, j, i) for (idx, i, j) in queries if res[idx] == -1]queries = sorted(queries, key=lambda x: indexes[x[2]])trigger = defaultdict(list)last_seen = defaultdict(int)for idx, i, j in queries:trigger[j].append((idx, i, j))last_seen[i] = idxlast_seen[j] = idxdef query(i, j):if i == j:return ir1, r2 = can_reach[i], can_reach[j]n, m = len(r1), len(r2)idx = bisect.bisect_left(r2, r1[0])if idx < m and r1[0] == r2[idx]:return r1[0]i = 0idx = bisect.bisect_left(r2, r1[-1])if idx >= m or r1[-1] != r2[idx]:return -1j = n-1while i < j-1:k = (i+j) // 2idx = bisect.bisect_left(r2, r1[k])if idx < m and r1[k] == r2[idx]:j = kelse:i = kreturn r1[j]s = []can_reach = {}for i, h in buildings:idx = bisect.bisect_left(s, i)s.insert(idx, i)if i in last_seen:can_reach[i] = s[idx:]for idx, i, j in trigger[i]:res[idx] = query(i, j)if last_seen[i] == idx:can_reach.pop(i)if j != i and last_seen[j] == idx:can_reach.pop(j)return res

提交代码评测得到：耗时5336ms，占用内存100.2MB。

3. 算法优化

看了一下大佬们的最优解答，发现在剪枝这部分大家其实思路是一致的，但是在那些复杂case的处理上大佬们的思路实在是太牛了。

他们的思路是直接使用堆排的方式，先将所需要比对的位置全部用一个堆排维护起来（其实用有序数列也行），然后考察每一个位置，看它能够作为那些位置的答案。

给出大佬们的实现方法如下：

class Solution:def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:m = len(queries)res = [-1] * mq = []left = [[] for _ in heights]for k, (i, j) in enumerate(queries):if i > j:i, j = j, iif i == j or heights[i] < heights[j]:res[k] = jelse:left[j].append((heights[i], k))h = []for i, x in enumerate(heights):while h and h[0][0] < x:k = heappop(h)[1]res[k] = ifor p in left[i]:heappush(h, p)return res

提交代码评测得到：耗时3680ms，占用内存39.5MB。