求最优解法：房屋数组销毁查询后的segment数量统计问题

题目描述 #

给定房屋位置数组（例如 houses = [1,2,3,7,8,10,11]）和查询数组（例如 q=[2,10,8]），按顺序执行每个查询（销毁指定位置的房屋），每次执行后返回当前剩余房屋的连续段数量。连续段定义为相邻房屋组成的组，单个无相邻房屋的房屋也视为一个连续段。

示例：

• 初始状态：剩余房屋形成3个连续段（[1,2,3]、[7,8]、[10,11]）
• 销毁房屋2后：剩余房屋为[1,3,7,8,10,11]，形成4个连续段
• 销毁房屋10后：剩余房屋为[1,3,7,8,11]，仍为4个连续段
• 销毁房屋8后：剩余房屋为[1,3,7,11]，还是4个连续段
• 最终结果数组：[4,4,4]

初始思路的局限 #

最初的思路是构建布尔数组，用索引对应房屋位置，存在房屋标记为True，否则False，每次查询时修改对应位置并计算连续段变化。但这种方法空间效率极低，当房屋位置范围极大（例如houses=[1,1000000]）时，布尔数组会占用大量不必要的空间。

优化解法：反向操作+哈希集合 #

核心思路 #

正向销毁房屋时，连续段数量可能增加或不变；反向操作则从“无查询销毁的最终状态”开始，逐步添加被查询销毁的房屋，此时连续段数量的变化逻辑更清晰（添加房屋只会减少、增加或保持连续段数），最后将结果反转即可得到正向执行的答案。

具体步骤 #

• 初始化数据结构：
  • 用哈希集合存储所有房屋位置，支持O(1)时间的存在性查询。
  • 用另一个哈希集合标记所有查询的房屋位置，区分“待添加”（反向）和“已保留”的房屋。
• 计算反向初始段数：
  • 遍历所有房屋，统计未被查询标记的房屋形成的连续段数量，这是反向操作的起点（对应正向操作的最终状态）。
• 反向处理查询：
  • 从最后一个查询倒序遍历，每次将当前查询的房屋位置“添加”回剩余房屋集合：
    1. 检查该位置的左邻居（pos-1）和右邻居（pos+1）是否在当前剩余集合中。
    2. 根据邻居存在情况更新连续段数：
       • 左右都不存在：添加后新增一个独立段，段数**+1**
       • 仅一个邻居存在：添加后合并到已有段，段数不变
       • 左右都存在：添加后将两个段合并为一个，段数**-1**
    3. 将当前段数记录到结果列表中。
• 反转结果：
  • 将反向处理得到的结果列表反转，即为正向执行每个查询后的连续段数数组。

复杂度分析 #

• 时间复杂度：O(N + Q)，其中N是房屋总数，Q是查询次数。遍历房屋统计初始段数、处理每个查询均为线性时间。
• 空间复杂度：O(N + Q)，仅需存储房屋集合和查询标记集合，避免了大范围布尔数组的空间浪费。

示例验证（反向操作） #

以题目示例为例：

1. 正向最终状态剩余房屋：[1,3,7,11]，段数为4。
2. 反向添加8：邻居7存在，11不存在，段数保持4。
3. 反向添加10：邻居8不存在，11存在，段数保持4。
4. 反向添加2：邻居1和3都存在，段数减1变为3。
5. 反向结果数组为[4,4,3]，反转后得到正向结果[4,4,4]，与示例一致。

内容的提问来源于stack exchange，提问作者Kiran Manicka