---

离散化

不改变数据相对大小的情况下，对数据进行相应的下标映射，即离散化。

例如：【100,200,300,400,500】，离散化后为【1,2,3,4,5】

什么时候可以离散化：当数据只与它们之间的相对大小有关，而与具体是多少无关

---

实战演练

LCP74.最强祝福力场 https://leetcode.cn/problems/xepqZ5/

提示：

数据范围1e9，该离散化技巧出山了

题解code：

class Solution:def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:x_set = set()y_set = set()for i, j, s in forceField:x_set.add(2 * i - s)y_set.add(2 * j - s)x_set.add(2 * i + s)y_set.add(2 * j + s)  # 通过*2来避免出现0.5这样的小数x_set_list = sorted(x_set)y_set_list = sorted(y_set)  # 集合转为列表m = len(x_set_list)n = len(y_set_list)# 初始化二位差分数组diff = [[0] * (n + 2) for _ in range(m + 2)]# 离散化：通过下标来映射for i, j, s in forceField:x1 = bisect_left(x_set_list, 2 * i - s) + 1y1 = bisect_left(y_set_list, 2 * j - s) + 1x2 = bisect_left(x_set_list, 2 * i + s) + 1y2 = bisect_left(y_set_list, 2 * j + s) + 1  # 通过二分查找得到下标# 二维差分diff[x1][y1] += 1diff[x2 + 1][y1] -= 1diff[x1][y2 + 1] -= 1diff[x2 + 1][y2 + 1] += 1ans = 0# 把二维差分数组还原为原数组for i in range(1, m + 2):for j in range(1, n + 2):diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]ans = max(ans, diff[i][j])return ans

涉及的二维差分可点此进入详细讲解
涉及的二分查找可点此进入详细讲解

总结

离散化的本质是一种哈希：将离散的数字（浮点数），转换成1-n
所有仅关注偏序关系的题目，均可以先离散化处理

---

如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢