城墙防线

标签:

难度: Medium

在探险营地间，小扣意外发现了一片城墙遗迹，在探索期间，却不巧遇到迁徙中的兽群向他迎面冲来。情急之下小扣吹响了他的苍蓝笛，随着笛声响起，遗迹中的城墙逐渐发生了横向膨胀。已知 `rampart[i] = [x,y]` 表示第 `i` 段城墙的初始所在区间。当城墙发生膨胀时，将遵循以下规则： - 所有的城墙会同时膨胀相等的长度； - 每个城墙可以向左、向右或向两个方向膨胀。小扣为了确保自身的安全，需要在所有城墙均无重叠的情况下，让城墙尽可能的膨胀。请返回城墙可以膨胀的 **最大值** 。 **注意：** - 初始情况下，所有城墙均不重叠，且 `rampart` 中的元素升序排列； - 两侧的城墙可以向外无限膨胀。 **示例 1：** >输入：`rampart = [[0,3],[4,5],[7,9]]` > >输出：`3` > >解释：如下图所示： >`rampart[0]` 向左侧膨胀 3 个单位； >`rampart[2]` 向右侧膨胀 3 个单位； >`rampart[1]` 向左侧膨胀 1 个单位，向右膨胀 2 个单位。 >不存在膨胀更多的方案，返回 3。 ![image.png](https://pic.leetcode.cn/1681717918-tWywrp-image.png){:width=750px} **示例 2：** >输入：`rampart = [[1,2],[5,8],[11,15],[18,25]]` > >输出：`4` **提示：** - `3 <= rampart.length <= 10^4` - `rampart[i].length == 2` - `0 <= rampart[i][0] < rampart[i][1] <= rampart[i+1][0] <= 10^8`

Submission

运行时间: 192 ms

内存: 20.0 MB

class Solution:
    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:
        lst = [rampart[i][0] - rampart[i-1][1] for i in range(1, len(rampart))]

        def check(num):
            temp = lst.copy()
            for i in range(len(temp) - 1):
                if temp[i] < 0:
                    return False
                if temp[i] < num:
                    temp[i + 1] -= (num - temp[i])
            return temp[-1] >= 0
        
        left = 0
        right = min(lst[i] + lst[i - 1] for i in range(1, len(lst)))
        while left < right:
            mid = (left + right + 1) // 2
            if check(mid):
                left = mid
            else:
                right = mid - 1
        return left

Explain

这个解法基于二分查找的方法来确定城墙可以膨胀的最大距离。首先，创建一个列表 `lst`，每个元素表示相邻城墙间的初始间隔。然后，定义一个辅助函数 `check(num)` 来验证给定的膨胀距离 `num` 是否可行，即是否能保持城墙间无重叠。`check` 函数通过逐个调整剩余的间隔来实现这一点。如果某个间隔小于 `num`，则从下一间隔中减去不足的部分。如果所有间隔都可以调整以满足条件，则返回 `True`。在主函数中，通过二分查找的方式不断调整 `num`，直到找到可能的最大膨胀距离。

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

空间复杂度: O(n)

class Solution:
    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:
        # 计算每对相邻城墙之间的初始间隔
        lst = [rampart[i][0] - rampart[i-1][1] for i in range(1, len(rampart))]

        # 辅助函数，用于检查给定的膨胀距离是否可行
        def check(num):
            temp = lst.copy() # 创建间隔列表的副本
            for i in range(len(temp) - 1):
                if temp[i] < 0:
                    return False
                if temp[i] < num:
                    temp[i + 1] -= (num - temp[i]) # 调整下一个间隔
            return temp[-1] >= 0

        # 二分查找最大可能的膨胀距离
        left = 0
        right = min(lst[i] + lst[i - 1] for i in range(1, len(lst)))
        while left < right:
            mid = (left + right + 1) // 2
            if check(mid):
                left = mid
            else:
                right = mid - 1
        return left

Explore

在`check`函数中使用`lst`的副本`temp`是为了保证每次调用`check`函数时`lst`都处于未被修改的初始状态。这样可以避免前一次调用`check`对`lst`的修改影响到后续的调用，确保每次`check`的判断都是基于相同的起始条件。如果直接在`lst`上操作，那么经过一次`check`后，`lst`中的数据可能会被永久改变，导致后续的二分查找逻辑错误。

选择`right`的初始值为`min(lst[i] + lst[i - 1] for i in range(1, len(lst)))`是为了确保我们不会从一个不可能成功的膨胀距离开始查找。这个值是基于考虑最短的两个连续间隔的和，因为最大可能的膨胀距离不可能超过任何两个间隔和的最小值。这样做可以有效减小二分查找的范围，提高算法的效率，同时避免不必要的`check`调用。

在二分查找中，当`check(mid)`返回`True`时，更新`left = mid`而不是`left = mid + 1`是为了保证不错过最大的可能值。这种做法是因为我们正在搜索最大的满足条件的`mid`。如果我们立即使用`left = mid + 1`，可能会在某些情况下跳过最大可能的膨胀距离。而更新`left = mid`确保了在下一次循环中，该`mid`值还有机会被再次考虑，从而确保找到真正的最大值。