python3 解法, 执行用时: 396 ms, 内存消耗: 20.7 MB, 提交时间: 2023-05-08 10:02:22

class Solution:
    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:
        l = 0
        r = float('inf')
        n = len(rampart)
        for i in range(1,n - 1):
            r = min(r,rampart[i][0] - rampart[i - 1][1] + rampart[i + 1][0] - rampart[i][1])
        
        def check(x):
            lst = rampart[0][1]
            for i in range(1,n - 1):
                left = rampart[i][0] - lst
                if left >= x:
                    lst = rampart[i][1]
                    continue
                cnt = x - left
                right = rampart[i + 1][0] - rampart[i][1]
                if right >= cnt:
                    lst = rampart[i][1] + cnt
                else:
                    return False
            return True
        
        while l <= r:
            mid = l + (r - l) // 2
            if check(mid):
                l = mid + 1
            else:
                r = mid - 1
        return l - 1

golang 解法, 执行用时: 156 ms, 内存消耗: 7.4 MB, 提交时间: 2023-05-08 10:01:57

func rampartDefensiveLine(rampart [][]int) (ans int) {
	n := len(rampart)
	leftSpace := rampart[n-1][0] - rampart[0][1]
	for _, p := range rampart[1 : n-1] {
		leftSpace -= p[1] - p[0]
	}
	return sort.Search(leftSpace/(n-2), func(mx int) bool {
		mx++
		preR := rampart[0][1]
		for i := 1; i < n-1; i++ {
			r := rampart[i][1]
			space := mx - (rampart[i][0] - preR)
			if space > 0 {
				r += space // 向右膨胀
				if r > rampart[i+1][0] { // 无法膨胀
					return true
				}
			}
			preR = r
	    }
	    return false
    })
}