本文最后更新于325 天前，其中的信息可能已经过时，如有错误请发送邮件到2446865563@qq.com
1.题目基本信息
1.1.题目描述
给你一个下标从 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.2.题目地址
2.解题方法
2.1.解题思路
方法一：线段树+二分查找
方法二：单调栈+二分查找
方法三：最小堆
2.2.解题步骤
单调栈+二分查找步骤：
-
第一步，构建维护变量。questions数组的questions[b]维护所有query=[a,b]时的(heights[a],b)数组（保证a<b）；result数组维护结果数组。
-
第二步，遍历queries，枚举为i,(a,b)。在保证a<=b的情况下，如果heights[a]<heights[b]或者a==b，则result[i]=b；否则将任务对(heights[a],i)添加到questions[b]中（记录i是为了确定是哪个query）。
-
第三步，使用stack维护heights[i+1:]区域的从左向右的单调递增的单调栈
最小堆步骤：
-
第一步，构建维护变量。questions数组的questions[b]维护所有query=[a,b]时的(heights[a],b)数组（保证a<b）；result数组维护结果数组。
-
第二步，遍历queries，枚举为i,(a,b)。在保证a<=b的情况下，如果heights[a]<heights[b]或者a==b，则result[i]=b；否则将任务对(heights[a],i)添加到questions[b]中（记录i是为了从堆中弹出时确定是哪个query）。
-
第三步，遍历heights，枚举为(i,x)。对于questions中i前面没有完成的任务，如果满足questions[*][1]<x，则i就是任务对questions[k]的题解，所以用一个最小堆维护遍历出的i前面的任务对，贪心的弹出比heights[i]小的任务对，并不断更新result数组。
线段树+二分查找步骤：
-
第一步，构建求区间最大值的线段树
-
第二步，线段树中递归的求[left,n-1]区间的第一个大于val的索引值
3.解题代码
线段树+二分方法代码
inf = float("inf")
class SegNode():
def __init__(self, id):
self.id = id
self.start = 0
self.end = 0
self.maxVal = -inf
self.lazy = 0
# ==> 带懒标记 使用Node结点 求范围最大值 的线段树【未经过题目测验，用了一个数组实验了一下】
class SegmentTree():
def __init__(self, nums:list[int]):
# 初始化线段树的存储数组并进行构建二叉平衡线段树（这里采用平衡二叉树，也可以用最大堆进行构建）
self.n = len(nums)
self.tree = [SegNode(i) for i in range(self.n * 4)] # 二叉平衡树的范围为4*n，如果使用最大堆的自底向上，则范围2*n即可
self.build(nums, 0, 0, self.n - 1)
# 基础方法：构建树，在node树中，将nums[start:end+1]中的区间元素进行插入（nodeId、start、end确定一个线段树结点）
def build(self, nums:list[int], nodeId:int, start:int, end:int) -> None:
node = self.tree[nodeId]
if start == end:
node.maxVal = nums[start]
node.start = start
node.end = end
return
mid = (end - start) // 2 + start
# 构建左子树
self.build(nums, nodeId * 2 + 1, start, mid)
# 构建右子树
self.build(nums, nodeId * 2 + 2, mid + 1, end)
# 最大值形式的线段树；tree[nodeId]记录nums[start:end+1]之间元素的最大值
node.maxVal = max(self.tree[nodeId * 2 + 1].maxVal, self.tree[nodeId * 2 + 2].maxVal)
node.start = start
node.end = end
# 结点懒标记向下推送（基础函数）：将node结点对象的懒标记推送到左右子结点中，并将自身的懒标记清空
def pushDown(self, node:SegNode) -> None:
# 第一步，特殊判断。node结点的懒标记值为0，无需向下推送，直接退出
if node.lazy == 0:
return
# 第二步，获取左右结点的结点编号和范围，更新左右结点对象的maxVal和lazy属性
start, end = node.start, node.end
mid = (end - start) // 2 + start
leftChild = self.tree[node.id * 2 + 1]
rightChild = self.tree[node.id * 2 + 2]
leftChild.maxVal += node.lazy
leftChild.lazy += node.lazy
rightChild.maxVal += node.lazy
rightChild.lazy += node.lazy
# 第三步，清空node对应的lazy值
node.lazy = 0
# 查询[left,n-1]区域中第一个比value大的元素位置
def query(self, value:int, left:int, nodeId:int) -> int:
node = self.tree[nodeId]
if node.maxVal <= value:
return -1
if node.start == node.end:
return node.start
self.pushDown(node)
leftNodeId = nodeId * 2 + 1
rightNodeId = nodeId * 2 + 2
leftNode = self.tree[leftNodeId]
rightNode = self.tree[rightNodeId]
if left <= leftNode.end:
pos = self.query(value, left, leftNodeId)
if pos >= 0:
return pos
return self.query(value, left, rightNodeId)
class Solution:
def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
# 思路：线段树+二分
segTree = SegmentTree(heights)
result = []
for a, b in queries:
if a > b:
a, b = b, a
if a == b or heights[a] < heights[b]:
result.append(b)
# print("test1", result[-1])
else:
result.append(segTree.query(heights[a], b, 0))
# print("test2", result[-1])
return result单调栈+二分方法代码
from bisect import bisect_right
class Solution:
def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
# 思路2：离线+单调栈
n = len(heights)
# 第一步，构建维护变量。questions数组的questions[b]维护所有query=[a,b]时的(heights[a],b)数组（保证a<b）；result数组维护结果数组。
result = [-1] * len(queries)
questions = [[] for _ in range(n)]
# 第二步，遍历queries，枚举为i,(a,b)。在保证a<=b的情况下，如果heights[a]<heights[b]或者a==b，则result[i]=b；否则将任务对(heights[a],i)添加到questions[b]中（记录i是为了确定是哪个query）。
for i, (a, b) in enumerate(queries):
if a > b:
a, b = b, a
if a == b or heights[a] < heights[b]:
result[i] = b
else:
questions[b].append((heights[a], i))
stack = []
# 第三步，使用stack维护heights[i+1:]区域的从左向右的单调递增的单调栈
for i in range(n - 1, -1, -1):
for val, j in questions[i]:
# 查询stack中第一个比val大的元素
index = bisect_right(stack, val, key = lambda x:heights[x])
if 0 <= index < len(stack):
result[j] = stack[index]
while stack and heights[i] >= heights[stack[0]]:
stack.pop(0)
stack.insert(0, i)
# print(stack)
# print([heights[l] for l in stack])
return result最小堆方法代码
from heapq import heappush, heappop, heapify
class Solution:
def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
# 思路：离线+最小堆
n = len(heights)
# 第一步，构建维护变量。questions数组的questions[b]维护所有query=[a,b]时的(heights[a],b)数组（保证a<b）；result数组维护结果数组。
result = [-1] * len(queries)
questions = [[] for _ in range(n)]
# 第二步，遍历queries，枚举为i,(a,b)。在保证a<=b的情况下，如果heights[a]<heights[b]或者a==b，则result[i]=b；否则将任务对(heights[a],i)添加到questions[b]中（记录i是为了从堆中弹出时确定是哪个query）。
for i, (a, b) in enumerate(queries):
if a > b:
a, b = b, a
if a == b or heights[a] < heights[b]:
result[i] = b
else:
questions[b].append((heights[a], i))
# 第三步，遍历heights，枚举为(i,x)。对于questions中i前面没有完成的任务，如果满足questions[*][1]<x，则i就是任务对questions[k]的题解，所以用一个最小堆维护遍历出的i前面的任务对，贪心的弹出比heights[i]小的任务对，并不断更新result数组。
heap = []
for i, x in enumerate(heights):
while heap and heap[0][0] < x:
val, j = heappop(heap)
result[j] = i
for q in questions[i]:
heappush(heap, q)
return result4.执行结果
