(离散化 + 二维差分) LCP 74. 最强祝福力场

LCP 74. 最强祝福力场

离散化 + 二维差分
灵茶山

• 坐标含0.5：坐标全部 * 2
• 离散化：x轴和y轴分别离散化
• 差分有个技巧，就是把坐标都 + 1，这样就不用单独处理第0行和第0列了，要额外写两个for循环。错误示范如第二份代码（我第一次写的。。）

class Solution(object):
    def fieldOfGreatestBlessing(self, forceField):
        """
        :type forceField: List[List[int]]
        :rtype: int
        """
        xs = []
        ys = []

        mp = {}
        
        for x, y, l in forceField:
            x *= 2
            y *= 2
            xs.append(x + l)
            xs.append(x - l)
            ys.append(y + l)
            ys.append(y - l)
        
        xs = sorted(xs)
        ys = sorted(ys)
        
        mpx = {v: i for i, v in enumerate(xs)}
        mpy = {v: i for i, v in enumerate(ys)}
        
        n = len(mpx)
        m = len(mpy)
        
        mat = [[0] * (m + 10) for _ in range(n  + 10)]
                
        for x, y, l in forceField:
            x *= 2
            y *= 2
            r1 = mpx[x - l] + 1
            r2 = mpx[x + l] + 1
            c1 = mpy[y - l] + 1
            c2 = mpy[y + l] + 1
            mat[r1][c1] += 1
            mat[r2 + 1][c1] -= 1
            mat[r1][c2 + 1] -= 1
            mat[r2 + 1][c2 + 1] += 1

        res = 0
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                mat[i][j] += mat[i - 1][j]
                mat[i][j] += mat[i][j - 1]
                mat[i][j] -= mat[i - 1][j - 1]
                res = max(res, mat[i][j])
            
        return res

额外多处理了第0行和第0列：

class Solution(object):
    def fieldOfGreatestBlessing(self, forceField):
        """
        :type forceField: List[List[int]]
        :rtype: int
        """
        xs = []
        ys = []

        mp = {}
        
        for x, y, l in forceField:
            x *= 2
            y *= 2
            xs.append(x + l)
            xs.append(x - l)
            ys.append(y + l)
            ys.append(y - l)
        
        xs = sorted(list(set(xs)))
        ys = sorted(list(set(ys)))
        
        mpx = {v: i for i, v in enumerate(xs)}
        mpy = {v: i for i, v in enumerate(ys)}
        
        n = len(mpx)
        m = len(mpy)
        
        mat = [[0] * (m + 2) for _ in range(n + 2)]
                
        for x, y, l in forceField:
            x *= 2
            y *= 2
            r1 = mpx[x - l]
            r2 = mpx[x + l]
            c1 = mpy[y - l]
            c2 = mpy[y + l]
            mat[r1][c1] += 1
            mat[r2 + 1][c1] -= 1
            mat[r1][c2 + 1] -= 1
            mat[r2 + 1][c2 + 1] += 1

        for i in range(1, n):
            mat[i][0] += mat[i - 1][0]
        for j in range(1, m):
            mat[0][j] += mat[0][j - 1]
        
        res = 0
        for i in range(1, n):
            for j in range(1, m):
                mat[i][j] += mat[i - 1][j]
                mat[i][j] += mat[i][j - 1]
                mat[i][j] -= mat[i - 1][j - 1]
                res = max(res, mat[i][j])
            
        return res