标签:
难度: Medium
标签:
难度: Medium
运行时间: 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
这个解法基于二分查找的方法来确定城墙可以膨胀的最大距离。首先,创建一个列表 `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
在`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`值还有机会被再次考虑,从而确保找到真正的最大值。