本文主要是介绍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 ⋅ l o g N ) O(N \cdot logN) O(N⋅logN)的时间复杂度能找到所有坐标上能够访问的所有位置。然后,剩下的问题就是如何去找到两个有序数列的最小公共元素。
这里,我做了个小trick,就是注意到了对于上述问题,显然如果两个序列有交集,那么显然,对于其中起始位置更高的那个序列(不妨记作序列A)而言,其最后一个元素必然也在另一个序列(不妨记作序列B)当中,且满足从某一个位置开始,必然有后方元素全在序列B当中,而其前方的序列均不在序列A当中。
由此,我们就可以使用一个二分搜索来快速找寻上述最小公共坐标了,所有query的时间复杂度也为 O ( N ⋅ l o g N ) O(N \cdot logN) O(N⋅logN)。
然而没有想到的是,这里居然遇到了内存爆炸的问题,就很懵逼……
这里,我是通过剪枝和及时删除的方法处理掉了这个问题,但是这里多少有点取巧了,而且非常的不优雅,就很难受了。
所谓剪枝倒是思路还挺自然,因为如果有两个坐标 i , j i,j i,j,满足 i = j i=j i=j或者 i < j i<j i<j且 h i < h j h_i < h_j hi<hj,那答案就是 j 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。
这篇关于Leetcode 2940. Find Building Where Alice and Bob Can Meet的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!