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
