网站的报价怎么做,网站被k怎么解决,中国空间站结构示意图,互联网金融营销案例LeetCode-day37-2940. 找到 Alice 和 Bob 可以相遇的建筑 题目描述示例示例1#xff1a;示例2#xff1a; 思路代码 题目描述
给你一个下标从 0 开始的正整数数组 heights #xff0c;其中 heights[i] 表示第 i 栋建筑的高度。
如果一个人在建筑 i #xff0c;且存在 i 示例2 思路代码 题目描述
给你一个下标从 0 开始的正整数数组 heights 其中 heights[i] 表示第 i 栋建筑的高度。
如果一个人在建筑 i 且存在 i j 的建筑 j 满足 heights[i] heights[j] 那么这个人可以移动到建筑 j 。
给你另外一个数组 queries 其中 queries[i] [ai, bi] 。第 i 个查询中Alice 在建筑 ai Bob 在建筑 bi 。
请你能返回一个数组 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 可以相遇的建筑。 思路
采用最小堆
算法涉及到三个位置假定 a≤b按照从左到右的顺序它们分别是
a回答询问时用其高度 heights[a] 和当前高度 heights[i] 比大小如果heights[a]heights[i] 则找到答案。b决定了在什么位置把询问加入堆中。注意在遍历到位置 b之前是不能入堆的。在遍历到位置 b 时入堆这样后续只需要比较 heights[a]heights[i]如果成立就间接地说明heights[b]heights[i] 也成立。并且由于我们是从左往右遍历 heights 的当前下标 i 就是 Alice 和Bob 可以相遇的最左边建筑的下标。回答询问的位置 i。如果堆顶 heights[a] 小于当前位置的高度heights[i]则回答堆顶询问并弹出堆顶。
代码
class Solution:def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) - List[int]:ans [-1] * len(queries)qs [[] for _ in heights]for i,(a,b) in enumerate(queries):if a b:a,b b,aif a b or heights[a]heights[b]:ans[i] belse:qs[b].append((heights[a],i))h []for i,x in enumerate(heights):while h and h[0][0] x:ans[heappop(h)[1]] ifor q in qs[i]:heappush(h,q)return ans
