找到爱丽丝和鲍勃可以见面的建筑物

2940。找到爱丽丝和鲍勃可以见面的建筑物

难度：难

主题：数组、二分查找、堆栈、二叉索引树、线段树、堆（优先级队列）、单调堆栈

给你一个0索引正整数高度数组，其中heights[i]代表第i^第建筑物的高度。

如果一个人在建筑物 i 中，当且仅当 i

您还会获得另一个数组查询，其中 requests[i] = [a_i, b_i]。在第 i^th 查询中，Alice 正在构建 a_i，而 Bob 正在构建 b_i。

返回一个数组 ans，其中 ans[i] 是 最左边建筑物的索引，Alice 和 Bob 可以在第 i^th 查询中相遇。如果 Alice 和 Bob 无法在查询 i 上移动到公共建筑物，请将 ans[i] 设置为 -1。

示例1：

• 输入： 高度 = [6,4,8,5,2,7]，查询 = [[0,1],[0,3],[2,4],[3,4] ,[2,2]]
• 输出： [2,5,-1,5,2]
• 解释： 在第一个查询中，Alice 和 Bob 可以移动到 2 号楼，因为 heights[0]
• 在第二个查询中，Alice 和 Bob 可以移动到 5 号楼，因为 heights[0]
• 在第三个查询中，Alice 无法见到 Bob，因为 Alice 无法移动到任何其他建筑物。
• 在第四个查询中，Alice 和 Bob 可以移动到 5 号楼，因为 heights[3]
• 在第五个查询中，Alice 和 Bob 已经在同一栋大楼中。
• 对于 ans[i] != -1，可以证明 ans[i] 是 Alice 和 Bob 可以见面的最左边的建筑物。
• 对于 ans[i] == -1，可以证明不存在 Alice 和 Bob 可以见面的建筑物。

示例2：

• 输入： 高度 = [5,3,8,2,6,1,4,6]，查询 = [[0,7],[3,5],[5,2],[ 3,0],[1,6]]
• 输出： [7,6,-1,4,6]
• 解释： 在第一个查询中，Alice 可以直接移动到 Bob 的建筑物，因为 heights[0]
• 在第二个查询中，Alice 和 Bob 可以移动到 6 号楼，因为 heights[3]
• 在第三个查询中，Alice 无法见到 Bob，因为 Bob 无法移动到任何其他建筑物。
• 在第四个查询中，Alice 和 Bob 可以移动到 4 号楼，因为 heights[3]
• 在第五个查询中，Alice 可以直接移动到 Bob 的建筑物，因为 heights[1]
• 对于 ans[i] != -1，可以证明 ans[i] 是 Alice 和 Bob 可以见面的最左边的建筑物。
• 对于 ans[i] == -1，可以证明不存在 Alice 和 Bob 可以见面的建筑物。

约束：

• 1 4
• 1 9
• 1 4
• 查询[i] = [a_i, b_i]
• 0 i, b_i

提示：

1. 对于每个查询 [x, y]，如果 x > y，交换x和y。现在，我们可以假设 x
2. 对于每个查询 [x, y]，如果 x == y 或 heights[x]
3. 否则，我们需要找到最小的索引 t 使得 y
4. 要找到每个查询的索引 t，请按 y 的降序对查询进行排序。迭代查询，同时维护单调堆栈，我们可以对其进行二分搜索以查找索引 t。

解决方案：

该问题需要根据爱丽丝和鲍勃的起始建筑物和移动规则确定最左边的建筑物，爱丽丝和鲍勃可以在其中相遇。每个查询都涉及根据建筑物高度查找交汇点。由于移动的限制和高效计算的需要，这是一个挑战。

要点

1. 爱丽丝和鲍勃可以移动到另一栋建筑，前提是该建筑的高度严格大于当前建筑。
2. 对于每个查询，找到最左边的有效集合点，如果不存在这样的建筑物，则返回-1。
3. 这些约束需要一个比简单的 O(n²) 方法更好的解决方案。

接近

1. 观察结果：

   • 如果 a == b，则 Alice 和 Bob 已经在同一栋楼了。
   • 如果高度[a]
   • 否则，找到最小的建筑索引 t >其中：
     • 高度[a]
     • heights[b]

2. 使用单调堆栈优化：

   • 单调堆栈有助于有效跟踪 Alice 和 Bob 可以移动到的有效建筑物。建筑物添加到堆栈中的方式确保高度按递减顺序排列，从而实现快速二进制搜索。

3. 查询排序：

   • 按 b 的降序对查询进行排序，以首先处理索引较大的建筑物。这确保了当我们从较高的索引移动到较低的索引时，我们可以有效地构建堆栈。

4. 堆栈上的二分查找：

   • 对于每个查询，在单调栈上使用二分查找来找到满足条件的最小索引t。

计划

1. 根据两个索引 (b) 中较大的一个按降序对查询进行排序。
2. 向后遍历数组，同时维护有效索引的单调堆栈。
3. 对于每个查询，检查简单情况（a == b 或 heights[a]
4. 对于重要的情况，使用堆栈通过二分搜索找到最左边的有效建筑物。
5. 按照原查询顺序返回结果。

解决步骤

1. 预处理查询：

   • 确保每个查询中的 a
   • 按 b 降序对查询进行排序。

2. 迭代查询：

   • 在遍历数组时保持单调堆栈。
   • 对于每个查询：
     • 如果 a == b，则答案为 b。
     • 如果高度[a]
     • 否则，使用堆栈查找最小的有效索引 t > b.

3. 堆栈上的二分查找：

   • 使用二分查找快速找到栈上满足heights[t] > 的最小索引t高度[a]。

4. 恢复原来的顺序：

   • 将结果映射回原始查询索引。

5. 返回结果。

让我们用 PHP 实现这个解决方案：2940。找到爱丽丝和鲍勃可以见面的建筑物

<?php
/**
 * @param Integer[] $heights
 * @param Integer[][] $queries
 * @return Integer[]
 */
function leftmostBuildingQueries($heights, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $queries
 * @return array
 */
private function getIndexedQueries($queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param $stack
 * @param $a
 * @param $heights
 * @return mixed|null
 */
private function findUpperBound($stack, $a, $heights) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

class IndexedQuery {
    public $queryIndex;
    public $a; // Alice's index
    public $b; // Bob's index

    /**
     * @param $queryIndex
     * @param $a
     * @param $b
     */
    public function __construct($queryIndex, $a, $b) {
        $this->queryIndex = $queryIndex;
        $this->a = $a;
        $this->b = $b;
    }
}

// Test the function
$heights = [6, 4, 8, 5, 2, 7];
$queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]];
print_r(leftmostBuildingQueries($heights, $queries));

$heights = [5, 3, 8, 2, 6, 1, 4, 6];
$queries = [[0, 7], [3, 5], [5, 2], [3, 0], [1, 6]];
print_r(leftmostBuildingQueries($heights, $queries));
?>

解释：

1. 排序查询： 查询按 b 降序排序，以首先处理较大的索引，这使我们能够在处理时更新单调堆栈。
2. 单调堆栈：堆栈用于跟踪爱丽丝和鲍勃可以见面的建筑索引。我们只保留高度比堆叠中任何先前见过的建筑物都大的建筑物。
3. 二分查找：在回答每个查询时，我们使用二分查找来有效地找到满足条件的最小索引 t。

示例演练

输入：

• 高度 = [6,4,8,5,2,7]
• 查询 = [[0,1],[0,3],[2,4],[3,4],[2,2]]

过程：

1. 排序查询：

   • 索引查询：[(2,4), (3,4), (0,3), (0,1), (2,2)]

2. 构建单调堆栈：

   • 从最高索引开始并将索引添加到堆栈中：
     • 在索引 5 处：堆栈 = [5]
     • 在索引 4 处：Stack = [5, 4]
     • ...

3. 查询处理：

   • 对于查询[0,1]，高度[0]
   • ...

输出：

[2, 5, -1, 5, 2]

时间复杂度

1. 查询排序： O(Q log Q)，其中 Q 是查询数量。
2. 单调堆栈构造： O(N)，其中 N 是高度的长度。
3. 每个查询的二分搜索： O(Q log N)。

总体： O(N Q log (Q N))。

示例输出

输入：

$heights = [6, 4, 8, 5, 2, 7];
$queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]];

输出：

print_r(findBuilding($heights, $queries)); // [2, 5, -1, 5, 2]

这种方法通过利用单调堆栈和二分搜索有效地处理大约束。它确保最佳查询处理，同时保持正确性。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是找到爱丽丝和鲍勃可以见面的建筑物的详细内容。更多信息请关注PHP中文网其他相关文章！