找到 Alice 和 Bob 可以相遇的建筑**
仅供学习
题目描述
一、第一版结果
可以找到结果，但是不能保证每次查找都是最左边位置
1.1 解题思路
使用动态规划来处理建筑的最远到达位置，并在此基础上处理查询。
1.2 优化方法
- 计算每个建筑能到达的最远建筑
- 使用动态规划来计算从每个建筑能到达的最远建筑。
- 处理查询：
- 对于每个查询，找出 Alice 和 Bob 的可到达范围的交集，并返回最左边的建筑。
1.3 实现步骤
- 计算每个建筑的最远到达建筑
- 使用 dp 数组来存储从每个建筑能够到达的最远建筑。
- 处理查询：
- 对于每个查询，检查 Alice 和 Bob 是否可以相遇，并返回最小的符合条件的建筑索引。
1.4 示例代码
以下是优化后的 Python 代码实现
def find_building(heights, queries): n = len(heights) # 动态规划计算每个建筑的最远到达建筑 farthest = list(range(n)) for i in range(n): j = i + 1 while j < n: if heights[j] > heights[i]: farthest[i] = j j += 1 results = [] # 处理每个查询 for ai, bi in queries: if ai >= n or bi >= n: results.append(-1) continue # 找到 Alice 能到达的范围 max_reach_alice = farthest[ai] for in_n in farthest[ai:]: if n < in_n or bi < in_n: break max_reach_alice = in_n print(ai, bi, max_reach_alice) # 找到 Bob 能到达的范围 max_reach_bob = farthest[bi] for in_n in farthest[bi:]: if n < in_n or ai < in_n: break max_reach_bob = in_n print(ai, bi, max_reach_bob) # 判断是否可以相遇 if max_reach_alice >= bi and max_reach_bob >= ai: results.append(min(max_reach_alice, max_reach_bob)) else: results.append(-1) return results
1.5 代码解释
- 计算最远到达建筑
- 使用动态规划（farthest 数组）来存储从每个建筑能够到达的最远建筑。
- 处理查询
- 对于每个查询，找到 Alice 和 Bob 能够相遇的最右边建筑。
