LCP 78. 城墙防线 

题目描述

在探险营地间，小扣意外发现了一片城墙遗迹，在探索期间，却不巧遇到迁徙中的兽群向他迎面冲来。情急之下小扣吹响了他的苍蓝笛，随着笛声响起，遗迹中的城墙逐渐发生了横向膨胀。已知 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。 {: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

解法

方法一：二分查找

我们注意到，如果一个膨胀值 $x$ 满足条件，那么所有小于 $x$ 的值也都满足条件，这存在着单调性。因此我们可以使用二分查找的方法，找到最大的满足条件的膨胀值。

我们定义二分查找的左边界 $left=0$, $right=rampart[1][0]-rampart[0][1]+rampart[2][0]-rampart[1][1]$，其中 $rampart[i][0]$ 表示第 $i$ 段城墙的左端点，$rampart[i][1]$ 表示第 $i$ 段城墙的右端点。

接下来，我们开始进行二分查找。每一次，我们求出当前的中间值 $mid$，并判断其是否满足条件。如果满足条件，那么我们就将左边界 $left$ 更新为 $mid$，否则将右边界 $right$ 更新为 $mid-1$。在二分查找结束后，我们返回左边界 $left$ 即可。

那么问题的关键在于如何判断一个值 $w$ 是否满足条件。显然，我们可以用贪心的策略，每次先尽可能往左膨胀，如果还有剩余的膨胀值，再往右膨胀，如果在向右膨胀的过程中，发生了重叠，那么说明当前的膨胀值 $w$ 不满足条件，直接返回 false 即可。否则，遍历结束，返回 true。

时间复杂度 $O(n \times \log M)$，其中 $n$ 和 $M$ 分别是数组 $rampart$ 的长度和二分查找的右边界，本题中右边界最大为 $range=rampart[1][0]-rampart[0][1]+rampart[2][0]-rampart[1][1]$。空间复杂度 $O(1)$。

Python3

class Solution:
    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:
        def check(w: int) -> bool:
            last = rampart[0][1]
            for i in range(1, len(rampart) - 1):
                x, y = rampart[i]
                a = x - last
                b = max(w - a, 0)
                if y + b > rampart[i + 1][0]:
                    return False
                last = y + b
            return True

        left, right = 0, rampart[1][0] - rampart[0][1] + rampart[2][0] - rampart[1][1]
        while left < right:
            mid = (left + right + 1) >> 1
            if check(mid):
                left = mid
            else:
                right = mid - 1
        return left

Java

class Solution {
    private int[][] rampart;

    public int rampartDefensiveLine(int[][] rampart) {
        this.rampart = rampart;
        int left = 0, right = rampart[1][0] - rampart[0][1] + rampart[2][0] - rampart[1][1];
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (check(mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    private boolean check(int w) {
        int last = rampart[0][1];
        for (int i = 1; i < rampart.length - 1; ++i) {
            int x = rampart[i][0], y = rampart[i][1];
            int a = x - last;
            int b = Math.max(w - a, 0);
            if (y + b > rampart[i + 1][0]) {
                return false;
            }
            last = y + b;
        }
        return true;
    }
}

C++

class Solution {
public:
    int rampartDefensiveLine(vector<vector<int>>& rampart) {
        int left = 0, right = rampart[1][0] - rampart[0][1] + rampart[2][0] - rampart[1][1];
        auto check = [&](int w) {
            int last = rampart[0][1];
            for (int i = 1; i < rampart.size() - 1; ++i) {
                int x = rampart[i][0], y = rampart[i][1];
                int a = x - last;
                int b = max(w - a, 0);
                if (y + b > rampart[i + 1][0]) {
                    return false;
                }
                last = y + b;
            }
            return true;
        };

        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (check(mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

Go

func rampartDefensiveLine(rampart [][]int) int {
	check := func(w int) bool {
		last := rampart[0][1]
		for i := 1; i < len(rampart)-1; i++ {
			x, y := rampart[i][0], rampart[i][1]
			a := x - last
			b := max(w-a, 0)
			if y+b > rampart[i+1][0] {
				return false
			}
			last = y + b
		}
		return true
	}

	left, right := 0, rampart[1][0]-rampart[0][1]+rampart[2][0]-rampart[1][1]
	for left < right {
		mid := (left + right + 1) >> 1
		if check(mid) {
			left = mid
		} else {
			right = mid - 1
		}
	}
	return left
}

TypeScript

function rampartDefensiveLine(rampart: number[][]): number {
    const check = (w: number): boolean => {
        let last = rampart[0][1];
        for (let i = 1; i < rampart.length - 1; ++i) {
            const [x, y] = rampart[i];
            const a = x - last;
            const b = Math.max(w - a, 0);
            if (y + b > rampart[i + 1][0]) {
                return false;
            }
            last = y + b;
        }
        return true;
    };
    let left = 0;
    let right = rampart[1][0] - rampart[0][1] + rampart[2][0] - rampart[1][1];
    while (left < right) {
        const mid = (left + right + 1) >> 1;
        if (check(mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}