搭桥过河

难度: Hard

欢迎各位勇者来到力扣城，本次试炼主题为「搭桥过河」。勇者面前有一段长度为 `num` 的河流，河流可以划分为若干河道。每条河道上恰有一块浮木，`wood[i]` 记录了第 `i` 条河道上的浮木初始的覆盖范围。 - 当且仅当浮木与相邻河道的浮木覆盖范围有重叠时，勇者才可以在两条浮木间移动 - 勇者 **仅能在岸上** 通过花费一点「自然之力」，使任意一条浮木沿着河流移动一个单位距离请问勇者跨越这条河流，最少需要花费多少「自然之力」。 **示例 1：** > 输入： `num = 10, wood = [[1,2],[4,7],[8,9]]` > 输出： `3` > 解释：如下图所示， > 将 [1,2] 浮木移动至 [3,4]，花费 2「自然之力」， > 将 [8,9] 浮木移动至 [7,8]，花费 1「自然之力」， > 此时勇者可以顺着 [3,4]->[4,7]->[7,8] 跨越河流， > 因此，勇者最少需要花费 3 点「自然之力」跨越这条河流 ![wood (2).gif](https://pic.leetcode-cn.com/1648196478-ophADL-wood%20\(2\).gif){:width=650px} **示例 2：** > 输入： `num = 10, wood = [[1,5],[1,1],[10,10],[6,7],[7,8]]` > 输出： `10` > 解释： > 将 [1,5] 浮木移动至 [2,6]，花费 1「自然之力」， > 将 [1,1] 浮木移动至 [6,6]，花费 5「自然之力」， > 将 [10,10] 浮木移动至 [6,6]，花费 4「自然之力」， > 此时勇者可以顺着 [2,6]->[6,6]->[6,6]->[6,7]->[7,8] 跨越河流， > 因此，勇者最少需要花费 10 点「自然之力」跨越这条河流 **示例 3：** > 输入： `num = 5, wood = [[1,2],[2,4]]` > 输出： `0` > 解释：勇者不需要移动浮木，仍可以跨越这条河流 **提示:** - `1 <= num <= 10^9` - `1 <= wood.length <= 10^5` - `wood[i].length == 2` - `1 <= wood[i][0] <= wood[i][1] <= num`

Submission

运行时间: 1073 ms

内存: 56.5 MB

class Solution:
    def buildBridge(self, num: int, wood: List[List[int]]) -> int:
        left_heap = []
        right_heap = []
        res = 0
        start_bias = 0
        end_bias = 0

        n = len(wood)
        for index in range(n):
            x, y = wood[index]
            if index == 0:
                left_heap.append(-x)
                right_heap.append(x)
            else:
                now_length = y - x
                last_length = wood[index - 1][1] - wood[index - 1][0]
                start_bias -= now_length
                end_bias += last_length

                now_start = -left_heap[0] + start_bias
                now_end = right_heap[0] + end_bias

                if x < now_start:
                    heappop(left_heap)
                    heappush(left_heap, start_bias - x)
                    heappush(left_heap, start_bias - x)
                    heappush(right_heap, now_start - end_bias)
                    res += now_start - x
                elif now_start <= x <= now_end:
                    heappush(left_heap, start_bias - x)
                    heappush(right_heap, x - end_bias)
                else:
                    heappop(right_heap)
                    heappush(right_heap, x - end_bias)
                    heappush(right_heap, x - end_bias)
                    heappush(left_heap, start_bias - now_end)
                    res += x - now_end

        return res

Explain

这道题目主要涉及到优化浮木位置使勇者可以跨越河流，使用最小的能量。思路是利用两个堆来跟踪浮木移动的范围。左堆（left_heap）负责跟踪当前浮木的最左端，而右堆（right_heap）跟踪最右端。在遍历每个浮木时，比较其位置与当前跨越范围（由堆维护），并相应地调整堆，并更新总花费的能量。如果当前浮木已在跨越范围内，则无需移动。如果浮木在跨越范围外，则需要移动到范围内，并更新堆和总花费。通过维护两个堆，可以在每次遍历时高效地找到需要的最左和最右的位置。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def buildBridge(self, num: int, wood: List[List[int]]) -> int:
        left_heap = []  # 用于维护当前覆盖区间的最左端点
        right_heap = []  # 用于维护当前覆盖区间的最右端点
        res = 0  # 记录总的移动花费
        start_bias = 0  # 记录左侧偏移量
        end_bias = 0  # 记录右侧偏移量

        n = len(wood)
        for index in range(n):
            x, y = wood[index]
            if index == 0:
                left_heap.append(-x)  # 初始化左堆
                right_heap.append(x)  # 初始化右堆
            else:
                now_length = y - x  # 当前浮木长度
                last_length = wood[index - 1][1] - wood[index - 1][0]  # 上一个浮木长度
                start_bias -= now_length  # 更新左偏移量
                end_bias += last_length  # 更新右偏移量

                now_start = -left_heap[0] + start_bias  # 计算当前最左端点
                now_end = right_heap[0] + end_bias  # 计算当前最右端点

                if x < now_start:  # 当前浮木在当前跨越区域左侧
                    heappop(left_heap)  # 移除堆顶元素
                    heappush(left_heap, start_bias - x)  # 更新左堆
                    heappush(right_heap, now_start - end_bias)  # 更新右堆
                    res += now_start - x  # 累加移动花费
                elif now_start <= x <= now_end:  # 当前浮木在跨越区域内
                    heappush(left_heap, start_bias - x)  # 更新左堆
                    heappush(right_heap, x - end_bias)  # 更新右堆
                else:  # 当前浮木在当前跨越区域右侧
                    heappop(right_heap)  # 移除堆顶元素
                    heappush(right_heap, x - end_bias)  # 更新右堆
                    heappush(left_heap, start_bias - now_end)  # 更新左堆
                    res += x - now_end  # 累加移动花费

        return res  # 返回最小的「自然之力」花费

Explore

在题解中，左堆（left_heap）用于维持当前可跨越范围的最左端点，而右堆（right_heap）维持最右端点。左堆为最大堆，右堆为最小堆。初始化时，将第一个浮木的左端点加入左堆（以负值形式存储以实现最大堆的效果），右端点加入右堆。堆的更新发生在浮木位置调整时。如果浮木需要向左移动以进入覆盖区间，左堆的堆顶（当前最左端点）被弹出，新的位置被压入。类似地，如果需要向右移动，右堆的堆顶被弹出，新的位置压入。这样确保了每次都可以快速地获取并更新覆盖区间的边界。

算法通过维护左右端点的最优位置（即当前最左和最右的位置），确保移动总距离最小化。堆结构使得每次都能快速访问和更新这些端点。尽管算法试图通过贪心策略保证每步移动都是局部最优，但不排除存在全局更优的解决方案。由于问题的复杂性及解空间的大小，可能需要更复杂的策略或算法（如动态规划）来找到绝对最优解。当前策略是实践中效率和实现的良好折中。

三种情况分别是：1）浮木在当前跨越区域的左侧，需要将浮木右移至至少覆盖区域的最左端。这时，左堆的堆顶被弹出，新位置加入左堆，右堆加入更新的最左端点，更新移动花费。例如，如果最左端是5，浮木左端是2，浮木被移动到5，总花费增加3。2）浮木在当前跨越区域内，无需移动，但需要更新左右堆以保持覆盖。3）浮木在当前跨越区域的右侧，需要左移至至少覆盖区域的最右端。这时右堆的堆顶被弹出，新位置加入右堆，左堆加入更新的最右端点，更新移动花费。例如，如果最右端是10，浮木右端是12，浮木被移动到10，总花费增加2。