2940. 找到 Alice 和 Bob 可以相遇的建筑

🔴   🔖  栈 树状数组 线段树 数组 二分查找 单调栈 堆（优先队列）  🔗 力扣 LeetCode

题目

You are given a 0-indexed array heights of positive integers, where heights[i] represents the height of the ith building.

If a person is in building i, they can move to any other building j if and only if i < j and heights[i] < heights[j].

You are also given another array queries where queries[i] = [ai, bi]. On the ith query, Alice is in building ai while Bob is in building bi.

Return an array ans where ans[i] isthe index of the leftmost building where Alice and Bob can meet on the ith query. If Alice and Bob cannot move to a common building on query i, set ans[i] to -1.

Example 1:

Input: heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]

Output: [2,5,-1,5,2]

Explanation: In the first query, Alice and Bob can move to building 2 since heights[0] < heights[2] and heights[1] < heights[2].

In the second query, Alice and Bob can move to building 5 since heights[0] < heights[5] and heights[3] < heights[5].

In the third query, Alice cannot meet Bob since Alice cannot move to any other building.

In the fourth query, Alice and Bob can move to building 5 since heights[3] < heights[5] and heights[4] < heights[5].

In the fifth query, Alice and Bob are already in the same building.

For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.

For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.

Example 2:

Input: heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]

Output: [7,6,-1,4,6]

Explanation: In the first query, Alice can directly move to Bob's building since heights[0] < heights[7].

In the second query, Alice and Bob can move to building 6 since heights[3] < heights[6] and heights[5] < heights[6].

In the third query, Alice cannot meet Bob since Bob cannot move to any other building.

In the fourth query, Alice and Bob can move to building 4 since heights[3] < heights[4] and heights[0] < heights[4].

In the fifth query, Alice can directly move to Bob's building since heights[1] < heights[6].

For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.

For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.

Constraints:

• 1 <= heights.length <= 5 * 10^4
• 1 <= heights[i] <= 10^9
• 1 <= queries.length <= 5 * 10^4
• queries[i] = [ai, bi]
• 0 <= ai, bi <= heights.length - 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：

输入： 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 * 10^4
• 1 <= heights[i] <= 10^9
• 1 <= queries.length <= 5 * 10^4
• queries[i] = [ai, bi]
• 0 <= ai, bi <= heights.length - 1

解题思路

1. 初始化：

   • 定义一个数组 res 来存储每个查询的答案，初始化为 -1。
   • 定义一个 store 数组来存储待处理的查询。

2. 处理每个查询：

   • 对于每个查询 [a, b]，如果满足以下条件，直接更新 res[i]。
     • 如果 a == b，意味着 Alice 和 Bob 在同一个建筑，相遇建筑编号为 a。
     • 如果 heights[a] < heights[b] 且 a < b，Alice 可以直接移动到 Bob，相遇建筑编号为 b。
     • 如果 heights[a] > heights[b] 且 a > b，Bob 可以直接移动到 Alice，相遇建筑编号为 a。
   • 否则，意味着 Alice 和 Bob 需要通过其他建筑相遇，将查询条件存储在 store 中，等待后续处理。
   • store 数组中的元素是按建筑编号进行存储的 store[minIndex] = [[minHeight, i]]，其中：
     • minIndex = Math.max(a, b)，代表相遇建筑的最小索引，只能在 a 和 b 右侧的建筑内相遇。
     • minHeight = Math.max(heights[a], heights[b])，代表相遇建筑的最小高度，只能在高度大于 a 和 b 高度的建筑内相遇。
     • i 是 [a, b] 在 queries 数组中的原始索引，方便根据原始索引回填结果。

3. 维护最小堆：

   • 使用最小堆维护所有待处理的查询，堆中的元素的优先级按 minHeight 从小到大排序。

4. 处理 store 中的查询

遍历所有的建筑，当遍历到某一建筑 i 时：

• 将 store[i] 中的查询条件添加到堆中（为了满足相遇建筑的索引大于 minIndex 的条件）

• 不断对比当前建筑的高度 heights[i] 和堆顶元素的高度 minHeight：

  • 当 heights[i] 比 minHeight 大时，意味着 Alice 或 Bob 可以移动到建筑 i 相遇，pop 出堆顶元素，更新查询结果 res。

5. 返回最终结果：
   • 遍历完所有建筑后，最终的 res 数组即为每个查询的答案。

复杂度分析

• 时间复杂度：O(n log n + q log n)，其中 n 是建筑数量，q 是查询数量。

  • 构造堆： 每个元素最多插入堆一次，堆的操作（插入、弹出）是 O(log n)，因此时间复杂度是 O(n log n)。
  • 遍历查询： 对每个查询，最多插入和弹出堆一次，时间复杂度是 O(q log n)。

• 空间复杂度：O(q + n)，

  • res 数组用来存储每个查询结果的数组，其长度等于查询数量 q，空间复杂度为 O(q)。
  • store 数组用于存储每个建筑对应的查询，最多有 q 个查询，空间复杂度为 O(q)。
  • 最小堆 minHeap 用于存储待处理的查询，堆中最多存储 n 个元素，空间复杂度是 O(n)。

代码

/**
 * @param {number[]} heights
 * @param {number[][]} queries
 * @return {number[]}
 */
var leftmostBuildingQueries = function (heights, queries) {
	const q = queries.length;
	const n = heights.length;

	let res = new Array(q).fill(-1); // 初始化结果数组，默认为 -1
	let store = new Array(n).fill().map(() => []); // 存储每个建筑的查询

	// 遍历查询
	queries.forEach(([a, b], i) => {
		// 基础条件：直接可以相遇
		if (a < b && heights[a] < heights[b]) {
			res[i] = b;
		} else if (a > b && heights[a] > heights[b]) {
			res[i] = a;
		} else if (a == b) {
			res[i] = a;
		} else {
			// 如果不能直接相遇，存储查询
			const minHeight = Math.max(heights[a], heights[b]); // 相遇建筑的最小高度
			const minIndex = Math.max(a, b); // 相遇建筑的最小索引
			store[minIndex].push([minHeight, i]); // 存储查询的信息
		}
	});

	// 定义最小堆的优先级：最低相遇建筑高度较小的查询排在前面
	const priority = (a, b) => a[0] < b[0];
	let minHeap = new MinHeap([], priority); // 初始化最小堆

	// 遍历建筑，更新查询结果
	for (let i = 0; i < n; i++) {
		// 将当前建筑的相关查询添加到堆中
		store[i].forEach((item) => minHeap.insert(item));

		// 每当建筑高度足够大时，更新堆中的查询结果
		while (!minHeap.isEmpty() && minHeap.getMin()[0] < heights[i]) {
			const item = minHeap.pop();
			res[item[1]] = i;
		}
	}

	return res;
};

// 最小堆实现
class MinHeap {
	constructor(arr = [], priority = (a, b) => a < b) {
		this.heap = arr;
		this.priority = priority;
		for (let i = ((this.heap.length / 2) | 0) - 1; i >= 0; i--) {
			this.heapifyDown(i);
		}
	}

	// 插入元素
	insert(item) {
		this.heap.push(item);
		this.heapifyUp(this.heap.length - 1);
	}

	// 移除并返回堆顶
	pop() {
		if (this.heap.length === 0) return null;
		const top = this.heap[0];
		const last = this.heap.pop();
		if (this.heap.length) {
			this.heap[0] = last;
			this.heapifyDown(0);
		}
		return top;
	}

	getMin() {
		return this.heap[0];
	}
	isEmpty() {
		return this.heap.length == 0;
	}

	heapifyUp(i) {
		while (i > 0) {
			const parent = ((i - 1) / 2) | 0;
			if (this.priority(this.heap[i], this.heap[parent])) {
				[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
				i = parent;
			} else {
				break;
			}
		}
	}

	heapifyDown(i) {
		const left = i * 2 + 1,
			right = i * 2 + 2;
		let min = i;
		if (
			left < this.heap.length &&
			this.priority(this.heap[left], this.heap[min])
		) {
			min = left;
		}
		if (
			right < this.heap.length &&
			this.priority(this.heap[right], this.heap[min])
		) {
			min = right;
		}
		if (min !== i) {
			[this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
			this.heapifyDown(min);
		}
	}
}

相关题目

题号	标题	题解	标签	难度	力扣
1642	可以到达的最远建筑		贪心 数组 堆（优先队列）	🟠	🀄️ 🔗
1944	队列中可以看到的人数		栈 数组 单调栈	🔴	🀄️ 🔗