2024-01-20：用go语言，小扣在探索丛林的过程中，无意间发现了传说中“落寞的黄金之都“， 而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场， 经过不断的勘测记录，

2024-01-20：用go语言，小扣在探索丛林的过程中，无意间发现了传说中"落寞的黄金之都"，

而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场，

经过不断的勘测记录，小扣将所有力场的分布都记录了下来，

forceField[i] = [x,y,side] ，

表示第 i 片力场将覆盖以坐标 (x,y) 为中心，边长为 side 的正方形区域。

若任意一点的 力场强度 等于覆盖该点的力场数量。

请求出在这片地带中 力场强度 最强处的 力场强度。

注意：力场范围的边缘同样被力场覆盖。

输入： forceField = [[0,0,1],[1,0,1]]。

输出：2。

来自lc的LCP 74. 最强祝福力场。

答案2024-01-20：

来自左程云。

灵捷3.5

大体过程如下：

1.定义一个变量n表示力场数量，初始化为forceField的长度。

2.创建两个空数组xs和ys，长度为n*2，用于存储力场覆盖区域的边界坐标。

3.遍历forceField，对于每个力场，将其中心坐标以及边长转换成边界坐标，并保存到xs和ys中。

4.对xs和ys进行排序。

5.去除xs和ys中的重复元素，并分别记录剩余元素的数量，得到sizex和sizey。

6.创建二维数组diff，大小为(sizex+2) x (sizey+2)，用于记录每个力场的覆盖数量。

7.遍历forceField，对于每个力场，找到其在xs和ys中对应的边界索引，并根据索引更新diff数组。

8.初始化变量ans为0，用于记录最大的力场强度。

9.使用动态规划的思想，从diff[1][1]开始遍历diff数组，依次计算每个位置的力场强度，并更新ans。

10.返回ans作为最大的力场强度。

总的时间复杂度：O(nlogn)，其中n为力场数量，排序的时间复杂度为O(nlogn)。

总的额外空间复杂度：O(n)，存储了xs和ys数组。

go完整代码如下：

package mainimport ("fmt""sort")func fieldOfGreatestBlessing(forceField [][]int) int {n := len(forceField)xs := make([]int64, n*2)ys := make([]int64, n*2)for i := 0; i < n; i++ {x := int64(forceField[i][0])y := int64(forceField[i][1])r := int64(forceField[i][2])xs[i*2] = (x << 1) - rxs[i*2+1] = (x << 1) + rys[i*2] = (y << 1) - rys[i*2+1] = (y << 1) + r}sort.Slice(xs, func(i, j int) bool { return xs[i] < xs[j] })sort.Slice(ys, func(i, j int) bool { return ys[i] < ys[j] })sizex := removeDuplicates(xs)sizey := removeDuplicates(ys)diff := make([][]int, sizex+2)for i := range diff {diff[i] = make([]int, sizey+2)}for i := 0; i < n; i++ {x := int64(forceField[i][0])y := int64(forceField[i][1])r := int64(forceField[i][2])a := binarySearch(xs, (x<<1)-r)b := binarySearch(ys, (y<<1)-r)c := binarySearch(xs, (x<<1)+r)d := binarySearch(ys, (y<<1)+r)set(diff, a, b, c, d)}ans := 0for i := 1; i < len(diff); i++ {for j := 1; j < len(diff[0]); j++ {diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]ans = max(ans, diff[i][j])}}return ans}func removeDuplicates(nums []int64) int {size := 1for i := 1; i < len(nums); i++ {if nums[i] != nums[size-1] {nums[size] = nums[i]size++}}return size}func binarySearch(nums []int64, v int64) int {l, r := 0, len(nums)-1var m, ans intfor l <= r {m = (l + r) / 2if nums[m] >= v {ans = mr = m - 1} else {l = m + 1}}return ans + 1}func set(diff [][]int, a, b, c, d int) {diff[a][b] += 1diff[c+1][d+1] += 1diff[c+1][b] -= 1diff[a][d+1] -= 1}func max(a, b int) int {if a > b {return a}return b}func main() {forceField := [][]int{{0, 0, 1}, {1, 0, 1}}result := fieldOfGreatestBlessing(forceField)fmt.Println(result)}