我最近遇到了一个 leetcode 风格的编程问题，我想知道解决它的最佳方法是什么。问题是这样的：
给定一个房屋数组（如 housing = [1,2,3,7,8,10,11]）和一组查询数组（如 q=[2,10,8]），返回存在多少个 segments 的数组每次查询后。每个查询都指示将被摧毁的房屋，并且查询按顺序执行。
段是指一组连续的房屋。从技术上讲，如果没有其他房屋与其连续（它没有邻居），那么一个分段中可以有一个房屋，但它仍然是一个分段。
例如。 房屋->[无，房屋，房屋，房屋，无，无，无，房屋，房屋，无，房屋，房屋]
可以看出，房屋指数是匹配的。在任何查询之前有 3 段（它们是粗体的） 第一次查询后，索引 2 处的房子将被销毁。
[无，房子，无，房子，无，无，无，房子，房子，无，房子，房子]
现在有4段，即res=[4]
下一次查询后，10号房屋被摧毁。
[无，房子，无，房子，无，无，无，房子，房子，无，无，房子]
还有4段。意味着 res=[4,4]
最后一次查询后，8号房屋被摧毁。
[无，房子，无，房子，无，无，无，房子，无，无，无，房子]
还有4段，表示res=[4,4,4]
由此返回的数组是[4,4,4]
我想知道解决这个问题的最佳方法是什么。我的做法是构造一个从 0 到房屋中最大元素的布尔数组，并将有房屋的索引设置为 True，将没有房屋的索引设置为 False。之后，对于每个查询，我们只需检查该索引并检查它有多少个邻居。如果有 0 个邻居，则段数减少 1，如果有 1 个邻居，则保持不变，如果有 2 个邻居，则段数增加 1。这种方法允许我在 O(1) 中处理查询，但它的空间效率不是很高，因为我们可能有一栋房子位于一个非常大的索引处，例如。房屋=[1,1000000]。有没有更好的方法来解决这个问题？预先感谢您。
你的解决方案是正确的，但是你使用大量空间在 O(1) 中查找的问题可以通过 HashMap 解决
在数组中的门牌号和索引之间创建一个 HashMap，对于每个查询，询问 HashMap 是否包含查询的编号，如果包含，则仅询问索引并在原始数组上使用邻居逻辑而不是布尔值数组。
如果数组中有多个具有相同编号的房屋，请在编号与具有相同逻辑的索引列表之间使用 HashMap，只需迭代列表而不是单个房屋。
该解决方案具有 O(|houses| + |queries|) 时间复杂度和 O(|houses|) 空间复杂度
这种方法是错误的，因为例如 h = 2, 4, 5, 6
如果我们销毁 2 那么 ans 应该是 1 并且根据你的逻辑如果它有一个 1 邻居它应该保持不变