class Solution {
public:
vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
}
};
2940. 找到 Alice 和 Bob 可以相遇的建筑
给你一个下标从 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 可以相遇的建筑。
提示：
1 <= heights.length <= 5 * 1041 <= heights[i] <= 1091 <= queries.length <= 5 * 104queries[i] = [ai, bi]0 <= ai, bi <= heights.length - 1原站题解
python3 解法, 执行用时: 694 ms, 内存消耗: 35.8 MB, 提交时间: 2024-08-10 12:08:34
class Solution:
def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
n = len(heights)
mx = [0] * (2 << n.bit_length())
# 用 heights 初始化线段树，维护区间最大值
def build(o: int, l: int, r: int) -> None:
if l == r:
mx[o] = heights[l]
return
m = (l + r) // 2
build(o * 2, l, m)
build(o * 2 + 1, m + 1, r)
mx[o] = max(mx[o * 2], mx[o * 2 + 1])
# 返回 [L,n-1] 中第一个 > v 的值的下标
# 如果不存在，返回 -1
def query(o: int, l: int, r: int, L: int, v: int) -> int:
if mx[o] <= v: # 区间最大值 <= v
return -1 # 没有 > v 的数
if l == r: # 找到了
return l
m = (l + r) // 2
if L <= m and (pos := query(o * 2, l, m, L, v)) >= 0: # 递归左子树
return pos
return query(o * 2 + 1, m + 1, r, L, v) # 递归右子树
build(1, 0, n - 1)
ans = []
for a, b in queries:
if a > b:
a, b = b, a # 保证 a <= b
if a == b or heights[a] < heights[b]:
ans.append(b) # a 直接跳到 b
else:
# 线段树二分，找 [b+1,n-1] 中的第一个 > heights[a] 的位置
ans.append(query(1, 0, n - 1, b + 1, heights[a]))
return ans
golang 解法, 执行用时: 244 ms, 内存消耗: 17.5 MB, 提交时间: 2023-11-21 21:50:54
func leftmostBuildingQueries(heights []int, queries [][]int) []int {
ans := make([]int, len(queries))
for i := range ans {
ans[i] = -1
}
left := make([][]pair, len(heights))
for qi, q := range queries {
i, j := q[0], q[1]
if i > j {
i, j = j, i // 保证 i <= j
}
if i == j || heights[i] < heights[j] {
ans[qi] = j // i 直接跳到 j
} else {
left[j] = append(left[j], pair{heights[i], qi}) // 离线
}
}
h := hp{}
for i, x := range heights { // 从小到大枚举下标 i
for h.Len() > 0 && h[0].h < x {
ans[heap.Pop(&h).(pair).qi] = i // 可以跳到 i（此时 i 是最小的）
}
for _, p := range left[i] {
heap.Push(&h, p) // 后面再回答
}
}
return ans
}
type pair struct{ h, qi int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].h < h[j].h }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
golang 解法, 执行用时: 220 ms, 内存消耗: 14.4 MB, 提交时间: 2023-11-21 21:50:28
type seg []int
func (t seg) build(a []int, o, l, r int) {
if l == r {
t[o] = a[l-1]
return
}
m := (l + r) >> 1
t.build(a, o<<1, l, m)
t.build(a, o<<1|1, m+1, r)
t[o] = max(t[o<<1], t[o<<1|1])
}
// 返回 [L,n] 中 > v 的最小下标（前三个参数表示线段树的节点信息）
func (t seg) query(o, l, r, L, v int) int {
if v >= t[o] { // 最大值 <= v，没法找到 > v 的数
return 0
}
if l == r { // 找到了
return l
}
m := (l + r) >> 1
if L <= m {
pos := t.query(o<<1, l, m, L, v) // 递归左子树
if pos > 0 { // 找到了
return pos
}
}
return t.query(o<<1|1, m+1, r, L, v) // 递归右子树
}
func leftmostBuildingQueries(heights []int, queries [][]int) []int {
n := len(heights)
t := make(seg, n*4)
t.build(heights, 1, 1, n)
ans := make([]int, len(queries))
for qi, q := range queries {
i, j := q[0], q[1]
if i > j {
i, j = j, i
}
if i == j || heights[i] < heights[j] {
ans[qi] = j
} else {
pos := t.query(1, 1, n, j+1, heights[i])
ans[qi] = pos - 1 // 不存在时刚好得到 -1
}
}
return ans
}
java 解法, 执行用时: 29 ms, 内存消耗: 70.5 MB, 提交时间: 2023-11-21 21:49:56
class Solution {
public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
int[] ans = new int[queries.length];
Arrays.fill(ans, -1);
List<int[]>[] left = new ArrayList[heights.length];
Arrays.setAll(left, e -> new ArrayList<>());
for (int qi = 0; qi < queries.length; qi++) {
int i = queries[qi][0], j = queries[qi][1];
if (i > j) {
int temp = i;
i = j;
j = temp; // 保证 i <= j
}
if (i == j || heights[i] < heights[j]) {
ans[qi] = j; // i 直接跳到 j
} else {
left[j].add(new int[]{heights[i], qi}); // 离线
}
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < heights.length; i++) { // 从小到大枚举下标 i
while (!pq.isEmpty() && pq.peek()[0] < heights[i]) {
ans[pq.poll()[1]] = i; // 可以跳到 i（此时 i 是最小的）
}
for (int[] p : left[i]) {
pq.offer(p); // 后面再回答
}
}
return ans;
}
public int[] leftmostBuildingQueries2(int[] heights, int[][] queries) {
int n = heights.length;
mx = new int[n * 4];
build(1, 1, n, heights);
int[] ans = new int[queries.length];
for (int qi = 0; qi < queries.length; qi++) {
int i = queries[qi][0], j = queries[qi][1];
if (i > j) {
int temp = i;
i = j;
j = temp;
}
if (i == j || heights[i] < heights[j]) {
ans[qi] = j;
} else {
int pos = query(1, 1, n, j + 1, heights[i]);
ans[qi] = pos - 1; // 不存在时刚好得到 -1
}
}
return ans;
}
private int[] mx;
private void build(int o, int l, int r, int[] heights) {
if (l == r) {
mx[o] = heights[l - 1];
return;
}
int m = (l + r) / 2;
build(o * 2, l, m, heights);
build(o * 2 + 1, m + 1, r, heights);
mx[o] = Math.max(mx[o * 2], mx[o * 2 + 1]);
}
// 返回 [L,n] 中 > v 的最小下标（前三个参数表示线段树的节点信息）
private int query(int o, int l, int r, int L, int v) {
if (v >= mx[o]) { // 最大值 <= v，没法找到 > v 的数
return 0;
}
if (l == r) { // 找到了
return l;
}
int m = (l + r) / 2;
if (L <= m) {
int pos = query(o * 2, l, m, L, v); // 递归左子树
if (pos > 0) { // 找到了
return pos;
}
}
return query(o * 2 + 1, m + 1, r, L, v); // 递归右子树
}
}
cpp 解法, 执行用时: 388 ms, 内存消耗: 174.9 MB, 提交时间: 2023-11-21 21:47:36
class Solution {
private:
vector<int> mx;
void build(int o, int l, int r, vector<int> &heights) {
if (l == r) {
mx[o] = heights[l - 1];
return;
}
int m = (l + r) / 2;
build(o * 2, l, m, heights);
build(o * 2 + 1, m + 1, r, heights);
mx[o] = max(mx[o * 2], mx[o * 2 + 1]);
}
// 返回 [L,n] 中 > v 的最小下标（前三个参数表示线段树的节点信息）
int query(int o, int l, int r, int L, int v) {
if (v >= mx[o]) { // 最大值 <= v，没法找到 > v 的数
return 0;
}
if (l == r) { // 找到了
return l;
}
int m = (l + r) / 2;
if (L <= m) {
int pos = query(o * 2, l, m, L, v); // 递归左子树
if (pos > 0) { // 找到了
return pos;
}
}
return query(o * 2 + 1, m + 1, r, L, v); // 递归右子树
}
public:
vector<int> leftmostBuildingQueries(vector<int> &heights, vector<vector<int>> &queries) {
int n = heights.size();
mx.resize(n * 4);
build(1, 1, n, heights);
vector<int> ans;
for (auto &q : queries) {
int i = q[0], j = q[1];
if (i > j) {
swap(i, j);
}
if (i == j || heights[i] < heights[j]) {
ans.push_back(j);
} else {
int pos = query(1, 1, n, j + 1, heights[i]);
ans.push_back(pos - 1); // 不存在时刚好得到 -1
}
}
return ans;
}
vector<int> leftmostBuildingQueries2(vector<int> &heights, vector<vector<int>> &queries) {
vector<int> ans(queries.size(), -1);
vector<vector<pair<int, int>>> left(heights.size());
for (int qi = 0; qi < queries.size(); qi++) {
int i = queries[qi][0], j = queries[qi][1];
if (i > j) {
swap(i, j); // 保证 i <= j
}
if (i == j || heights[i] < heights[j]) {
ans[qi] = j; // i 直接跳到 j
} else {
left[j].emplace_back(heights[i], qi); // 离线
}
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
for (int i = 0; i < heights.size(); i++) { // 从小到大枚举下标 i
while (!pq.empty() && pq.top().first < heights[i]) {
ans[pq.top().second] = i; // 可以跳到 i（此时 i 是最小的）
pq.pop();
}
for (auto &p: left[i]) {
pq.emplace(p); // 后面再回答
}
}
return ans;
}
};
python3 解法, 执行用时: 288 ms, 内存消耗: 39.4 MB, 提交时间: 2023-11-21 21:46:15
class Solution:
def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
ans = [-1] * len(queries)
left = [[] for _ in heights]
for qi, (i, j) in enumerate(queries):
if i > j:
i, j = j, i # 保证 i <= j
if i == j or heights[i] < heights[j]:
ans[qi] = j # i 直接跳到 j
else:
left[j].append((heights[i], qi)) # 离线
h = []
for i, x in enumerate(heights): # 从小到大枚举下标 i
while h and h[0][0] < x:
ans[heappop(h)[1]] = i # 可以跳到 i（此时 i 是最小的）
for p in left[i]:
heappush(h, p) # 后面再回答
return ans
def leftmostBuildingQueries2(self, heights: List[int], queries: List[List[int]]) -> List[int]:
n = len(heights)
mx = [0] * (n * 4)
def build(o: int, l: int, r: int) -> None:
if l == r:
mx[o] = heights[l - 1]
return
m = (l + r) // 2
build(o * 2, l, m)
build(o * 2 + 1, m + 1, r)
mx[o] = max(mx[o * 2], mx[o * 2 + 1])
# 返回 [L,n] 中 > v 的最小下标（前三个参数表示线段树的节点信息）
def query(o: int, l: int, r: int, L: int, v: int) -> int:
if v >= mx[o]: # 最大值 <= v，没法找到 > v 的数
return 0
if l == r: # 找到了
return l
m = (l + r) // 2
if L <= m:
pos = query(o * 2, l, m, L, v) # 递归左子树
if pos > 0: # 找到了
return pos
return query(o * 2 + 1, m + 1, r, L, v) # 递归右子树
build(1, 1, n)
ans = []
for i, j in queries:
if i > j:
i, j = j, i
if i == j or heights[i] < heights[j]:
ans.append(j)
else:
pos = query(1, 1, n, j + 1, heights[i])
ans.append(pos - 1) # 不存在时刚好得到 -1
return ans