java 解法, 执行用时: 14 ms, 内存消耗: 41.8 MB, 提交时间: 2023-04-23 10:44:46

class Solution {
	int[][] diff;
	int m, n;
	
    public int fieldOfGreatestBlessing(int[][] forceField) {
		// 1. 统计所有左下和右上坐标
		var xSet = new HashSet<Long>();
		var ySet = new HashSet<Long>();
		int i = 0, j = 0, side = 0;
		for(int[] f : forceField) {
		    i = f[0];
		    j = f[1];
			side = f[2];

			xSet.add(1l * 2 * i - side); //由于会出现0.5, 所以将坐标乘 2
			xSet.add(1l * 2 * i + side);

			ySet.add(1l * 2 * j - side);
			ySet.add(1l * 2 * j + side);
		}

		// 2. 离散化
		int m = xSet.size(), n = ySet.size();
		var xs = new ArrayList<Long>();
		for(long e : xSet) xs.add(e);
		Collections.sort(xs, (a, b)->a.compareTo(b));
			
		var ys = new ArrayList<Long>();
		for(long e : ySet) ys.add(e);
		Collections.sort(ys, (a, b)->a.compareTo(b));

		// 3. 二维差分
		diff = new int[m + 2][n + 2];
		long x = 0, y = 0;
		int r1 = 0, r2 = 0, c1 = 0, c2 = 0;

		for(int[] p : forceField){
			i = p[0];
			j = p[1];
			side = p[2];
			x = 2 * 1l * i - side;
			y = 2 * 1l * j - side;
			r1 = binarySearch(xs, x);
            c1 = binarySearch(ys, y);


			x = 2 * 1l * i + side;
			y = 2 * 1l * j + side;
			r2 = binarySearch(xs, x);
			c2 = binarySearch(ys, y);

			update(r1, c1, r2, c2);
		}

		// 4. 计算最大值
		int res = 0;
		for(i = 1; i <= m; ++i) {
			for(j = 1; j <= n; ++j){
				//前缀和公式
				diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
				res = Math.max(res, diff[i][j]);
			}
		}
		return res;
    }
        
	public void update(int r1, int c1, int r2, int c2) {
		++diff[r1 + 1][c1 + 1];
        ++diff[r2 + 2][c2 + 2];
		--diff[r2 + 2][c1 + 1];
		--diff[r1 + 1][c2 + 2];
	}
	
	public int binarySearch(List<Long> arr, long t) {
		 int mid = 0;
		 int l = -1, r = arr.size();
		 while(l + 1 < r){
			mid = (l + r) >>> 1;
			if(Long.compare(arr.get(mid), t) < 0) l = mid;
			else r = mid;
		 }
		 return r;
	}
}

cpp 解法, 执行用时: 20 ms, 内存消耗: 10.2 MB, 提交时间: 2023-04-23 10:39:05

#define ll long long
class Solution {
public:
    int fieldOfGreatestBlessing(vector<vector<int>>& forceField) {
       	int ans = 0;
        set<ll>x_set;
        set<ll>y_set;
		for(auto&p : forceField){
            ll i = p[0], j = p[1], len = p[2];
            ll x2 = 2 * i + len, x1 = 2 * i - len;
            ll y2 = 2 * j + len, y1 = 2 * j - len;
            x_set.insert(x1), x_set.insert(x2);
            y_set.insert(y1), y_set.insert(y2);
        } 
        vector<ll>ax{x_set.begin(), x_set.end()};
        vector<ll>ay{y_set.begin(), y_set.end()};
        auto find = [&](auto & nums, ll val){
            return lower_bound(nums.begin(), nums.end(), val) - nums.begin();
        };
        int n = ax.size(), m = ay.size();
        int diff[n + 2][m + 2];
        memset(diff, 0, sizeof(diff));
        for(auto& p : forceField){
            ll i = p[0], j = p[1], len = p[2];
            ll x2 = 2 * i + len, x1 = 2 * i - len;
            ll y2 = 2 * j + len, y1 = 2 * j - len;
            x2 = find(ax, x2), x1 = find(ax, x1);
            y2 = find(ay, y2), y1 = find(ay, y1);
            diff[x1 + 1][y1 + 1]++;
            diff[x2 + 2][y1 + 1]--;
            diff[x1 + 1][y2 + 2]--;
            diff[x2 + 2][y2 + 2]++;
        }
        for(int i = 1; i <= n;++i){
            for(int j = 1; j <= m;++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;
    }
};

python3 解法, 执行用时: 232 ms, 内存消耗: 15.5 MB, 提交时间: 2023-04-23 10:38:25

class Solution:
    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:
        # 1.统计所有左下和右上坐标
        xSet = set()
        ySet = set()
        for f in forceField:
            i, j, side = f[0], f[1], f[2]
            x = 2 * i - side
            y = 2 * j - side
            xSet.add(x)
            ySet.add(y)
            x = 2 * i + side
            y = 2 * j + side
            xSet.add(x)
            ySet.add(y)
    
        # 2.离散化
        xs = sorted(list(xSet))
        ys = sorted(list(ySet))
    
        # 3.二维差分
        n, m = len(xs), len(ys)
        diff = [[0] * (m + 2) for _ in range(n + 2)]
    
        def update(r1, c1, r2, c2):
            diff[r1 + 1][c1 + 1] += 1
            diff[r1 + 1][c2 + 2] -= 1
            diff[r2 + 2][c1 + 1] -= 1
            diff[r2 + 2][c2 + 2] += 1
    
        for p in forceField:
            i, j, side = p[0], p[1], p[2]
            x = 2 * i - side
            y = 2 * j - side
            r1 = xs.index(x)
            c1 = ys.index(y)
            x = 2 * i + side
            y = 2 * j + side
            r2 = xs.index(x)
            c2 = ys.index(y)
            update(r1, c1, r2, c2)
            
        # 4.复原，计算最大值
        ans = 0
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]
                ans = max(ans, diff[i][j]) if ans < diff[i][j] else ans
    
        return ans

golang 解法, 执行用时: 8 ms, 内存消耗: 6.6 MB, 提交时间: 2023-04-23 10:37:24

func fieldOfGreatestBlessing(forceField [][]int) (ans int) {
	// 1. 统计所有左下和右上坐标
	xSet := map[int]bool{}
	ySet := map[int]bool{}
	for _, f := range forceField {
		i, j, side := f[0], f[1], f[2]
		x := 2*i - side
		y := 2*j - side
		xSet[x] = true
		ySet[y] = true
		x = 2*i + side
		y = 2*j + side
		xSet[x] = true
		ySet[y] = true
	}

	// 2. 离散化
	n, m := len(xSet), len(ySet)
	xs := make([]int, 0, n)
	for x := range xSet {
		xs = append(xs, x)
	}
	sort.Ints(xs)
	ys := make([]int, 0, m)
	for y := range ySet {
		ys = append(ys, y)
	}
	sort.Ints(ys)

	// 3. 二维差分
	diff := make([][]int, n+2)
	for i := range diff {
		diff[i] = make([]int, m+2)
	}
	update := func(r1, c1, r2, c2 int) {
		diff[r1+1][c1+1]++
		diff[r1+1][c2+2]--
		diff[r2+2][c1+1]--
		diff[r2+2][c2+2]++
	}
	for _, p := range forceField {
		i, j, side := p[0], p[1], p[2]
		x := 2*i - side
		y := 2*j - side
		r1 := sort.SearchInts(xs, x)
		c1 := sort.SearchInts(ys, y)
		x = 2*i + side
		y = 2*j + side
		r2 := sort.SearchInts(xs, x)
		c2 := sort.SearchInts(ys, y)
		update(r1, c1, r2, c2)
	}

	// 4. 复原，计算最大值
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			diff[i][j] += diff[i][j-1] + diff[i-1][j] - diff[i-1][j-1]
			ans = max(ans, diff[i][j])
		}
	}
	return
}

func max(a, b int) int { if a < b { return b }; return a }