最强祝福力场

标签:

难度: Medium

小扣在探索丛林的过程中，无意间发现了传说中“落寞的黄金之都”。而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场。 经过不断的勘测记录，小扣将所有力场的分布都记录了下来。`forceField[i] = [x,y,side]` 表示第 `i` 片力场将覆盖以坐标 `(x,y)` 为中心，边长为 `side` 的正方形区域。 若任意一点的 **力场强度** 等于覆盖该点的力场数量，请求出在这片地带中 **力场强度** 最强处的 **力场强度**。 **注意：** - 力场范围的边缘同样被力场覆盖。 **示例 1：** >输入： >`forceField = [[0,0,1],[1,0,1]]` > >输出：`2` > >解释：如图所示，（0.5, 0) 处力场强度最强为 2， （0.5，-0.5）处力场强度同样是 2。 ![image.png](https://pic.leetcode.cn/1681805536-zGfghe-image.png){:width=400px} **示例 2：** >输入： >`forceField = [[4,4,6],[7,5,3],[1,6,2],[5,6,3]]` > >输出：`3` > >解释：如下图所示， >`forceField[0]、forceField[1]、forceField[3]` 重叠的区域力场强度最大，返回 `3` ![image.png](https://pic.leetcode.cn/1681805437-HQkyZS-image.png){:width=500px} **提示：** - `1 <= forceField.length <= 100` - `forceField[i].length == 3` - `0 <= forceField[i][0], forceField[i][1] <= 10^9` - `1 <= forceField[i][2] <= 10^9`

Submission

运行时间: 103 ms

内存: 16.0 MB

class Solution:
    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:
        res = 0
        lines = []
        s = set()
        for x, y, side in forceField:
            x1 = x * 2 - side
            x2 = x * 2 + side
            lines.append((y * 2 - side, -1, x1, x2))
            lines.append((y * 2 + side, 1, x1, x2))
            s.add(x1)
            s.add(x2)
        lines.sort()
        for x in s:
            count = 0
            for y, flag, x1, x2 in lines:
                if x1 <= x <= x2:
                    count -= flag
                    res = max(res, count)
        return res

Explain

此题解采用了扫描线和事件处理的技术来解决问题。首先，为每个力场定义两个事件：开始和结束。这些事件定义了力场的垂直边界。每个力场由中心点(x, y)和边长side给出，我们可以计算出力场在x轴上的起始x1和结束x2位置，以及在y轴上的起始和结束位置。将y轴视作扫描线，对所有事件按y坐标排序，然后逐个处理这些事件。同时，我们使用一个集合s来存储所有不同的x坐标点，以便在处理每个y坐标时，能够检查哪些x坐标处的力场强度可能达到最大值。对于每个独特的x坐标，我们检查该点是否在当前活动的力场内，并相应地更新该点的力场强度计数。通过遍历所有事件，可以找到所有点的最大力场强度。

时间复杂度: O(n log n + nx)

空间复杂度: O(n)

class Solution:
    def fieldOfGreatestBlessing(self, forceField: List[List[int]]) -> int:
        res = 0  # 最大力场强度
        lines = []  # 存储所有事件
        s = set()  # 存储所有独特的x坐标
        # 构建事件
        for x, y, side in forceField:
            x1 = x * 2 - side  # 计算力场在x轴的起始位置
            x2 = x * 2 + side  # 计算力场在x轴的结束位置
            lines.append((y * 2 - side, -1, x1, x2))  # 添加开始事件
            lines.append((y * 2 + side, 1, x1, x2))  # 添加结束事件
            s.add(x1)  # 添加独特的x坐标
            s.add(x2)
        # 根据y坐标排序事件
        lines.sort()
        # 处理每个独特的x坐标
        for x in s:
            count = 0  # 当前x坐标的力场强度计数
            # 处理所有事件，更新力场强度计数
            for y, flag, x1, x2 in lines:
                if x1 <= x <= x2:
                    count -= flag  # 根据事件类型更新计数
                    res = max(res, count)  # 更新最大力场强度
        return res

Explore

扫描线和事件处理技术是一种有效处理几何问题的方法，特别是涉及到多个区域或形状的覆盖和交集问题。在这个题解中，每个力场视为一个矩形区域，我们通过定义每个矩形的开始和结束事件（即矩形的上下边界），来追踪扫描线（y轴）的移动。当扫描线遇到一个矩形的开始边界时，这个矩形被认为是'活动的'；当扫描线超过结束边界时，这个矩形不再被考虑。通过这种方式，我们可以在每个y坐标的扫描时跟踪哪些矩形是活动的，进而计算每个x坐标的最大力场强度。这样做的好处是能够高效地处理和更新大量区域的交叠情况，尤其是在计算复杂度和数据结构操作上更为高效。

题解中将'y * 2 - side'和'y * 2 + side'用作事件的y坐标是为了确保整数坐标处理的精确性和一致性。由于题目中给出的力场中心点(x, y)和边长可能导致计算出的x1和x2坐标为小数，通过乘以2，我们可以保持所有坐标的整数状态，避免处理浮点数带来的不精确性。此外，这种处理方式确保了在不同力场边界值的计算上保持一致，使得扫描线可以精确地识别和处理每一个力场的开始和结束，从而正确地更新覆盖区域和力场强度。

使用集合s来存储所有独特的x坐标是为了确保在计算每个x坐标处的最大力场强度时不会出现重复计算。然而，这种方法在所有x坐标高度集中或重复较少时效率最低，因为它需要对每个独特的x坐标进行相同的计算，而这可能涉及大量不必要的操作。更优的数据结构选择可能包括平衡二叉搜索树（如AVL树或红黑树），这种结构可以更高效地处理范围查询和更新操作，尤其是在动态添加或删除x坐标点时，能保持较低的时间复杂度。此外，使用线段树或树状数组可以在一定程度上优化区间内最大值的查询和更新效率。