最多可以摧毁的敌人城堡数目

标签: 数组双指针

难度: Easy

给你一个长度为 n ，下标从 0 开始的整数数组 forts ，表示一些城堡。forts[i] 可以是 -1 ，0 或者 1 ，其中：

-1 表示第 i 个位置没有城堡。
0 表示第 i 个位置有一个敌人的城堡。
1 表示第 i 个位置有一个你控制的城堡。

现在，你需要决定，将你的军队从某个你控制的城堡位置 i 移动到一个空的位置 j ，满足：

0 <= i, j <= n - 1
军队经过的位置只有敌人的城堡。正式的，对于所有 min(i,j) < k < max(i,j) 的 k ，都满足 forts[k] == 0 。

当军队移动时，所有途中经过的敌人城堡都会被摧毁。

请你返回最多可以摧毁的敌人城堡数目。如果无法移动你的军队，或者没有你控制的城堡，请返回 0 。

示例 1：

输入：forts = [1,0,0,-1,0,0,0,0,1]
输出：4
解释：
- 将军队从位置 0 移动到位置 3 ，摧毁 2 个敌人城堡，位置分别在 1 和 2 。
- 将军队从位置 8 移动到位置 3 ，摧毁 4 个敌人城堡。
4 是最多可以摧毁的敌人城堡数目，所以我们返回 4 。

示例 2：

输入：forts = [0,0,1,-1]
输出：0
解释：由于无法摧毁敌人的城堡，所以返回 0 。

提示：

1 <= forts.length <= 1000
-1 <= forts[i] <= 1

Submission

运行时间: 20 ms

内存: 16.6 MB

class Solution(object):
    def captureForts(self, forts):
        ans = 0
        n = len(forts)
        i = 0
        while i < n:
            if forts[i] == 1:
                i += 1
                curr = 0
                while i < n and forts[i] == 0:
                    curr += 1
                    i += 1
                if i < n and forts[i] == -1:
                    ans = max(ans, curr)
                i -= 1
            if forts[i] == -1:
                i += 1
                curr = 0
                while i < n and forts[i] == 0:
                    curr += 1
                    i += 1
                if i < n and forts[i] == 1:
                    ans = max(ans, curr)
                i -= 1
            i += 1
        return ans

Explain

这个题解的主要思路是遍历数组 `forts`，寻找从你控制的城堡（值为1）到空位（值为-1），或从空位到你控制的城堡的路径上最多可以摧毁的敌人城堡（值为0）。具体方法是，当遇到你控制的城堡或空位时，开始向后寻找连续的敌人城堡，直到遇到另一个空位或你控制的城堡。如果这段连续敌人城堡的终点是空位或你控制的城堡，则计算这段路径上敌人城堡的数量，并更新最大值。这种方法确保了每个可能的路径都被检查，从而找到最大的可以摧毁的敌人城堡数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution(object):
    def captureForts(self, forts):
        ans = 0  # 用于存储最大可以摧毁的敌人城堡数量
        n = len(forts)  # 数组的长度
        i = 0  # 初始索引
        while i < n:  # 遍历数组
            if forts[i] == 1:  # 从你控制的城堡开始
                i += 1
                curr = 0  # 当前连续敌人城堡数
                while i < n and forts[i] == 0:  # 计算连续的敌人城堡数
                    curr += 1
                    i += 1
                if i < n and forts[i] == -1:  # 结束于空位
                    ans = max(ans, curr)
                i -= 1  # 回退一步，检查下一个位置
            if forts[i] == -1:  # 从空位开始
                i += 1
                curr = 0  # 当前连续敌人城堡数
                while i < n and forts[i] == 0:  # 计算连续的敌人城堡数
                    curr += 1
                    i += 1
                if i < n and forts[i] == 1:  # 结束于你控制的城堡
                    ans = max(ans, curr)
                i -= 1  # 回退一步，检查下一个位置
            i += 1  # 移至下一个位置
        return ans  # 返回最大可以摧毁的敌人城堡数量

Explore

题解中的算法在计算连续敌人城堡数量时，确实没有明确指出如何处理连续城堡出现在数组末尾并且未遇到-1或1的情况。在这种情况下，根据题目要求，敌人城堡的摧毁必须以你控制的城堡或空位结束。因此，如果连续的敌人城堡到达数组末尾时没有遇到-1或1，则这部分城堡不应被计入可摧毁的城堡数量。算法应该只统计那些在遇到-1或1时结束的连续敌人城堡数量。

在题解中，算法在检查完一个可能的路径后需要将索引i回退一步是为了确保不遗漏任何可能的起始点。例如，如果在检查从某个你控制的城堡到一个空位的路径后，当前的索引i指向了下一个位置，这可能会跳过一个重要的起始点（如另一个你控制的城堡或空位）。回退一步可以确保在下一次迭代时，算法从当前检查结束的位置重新开始，以便捕捉所有可能的起始点，确保每个可能的路径都被彻底检查。

题解中从你控制的城堡或空位作为起始点开始寻找连续的敌人城堡，这种做法确保了算法覆盖所有可能的有效路径。然而，这种起始点的选择也可能导致某些路径被重复计算。例如，如果一个连续敌人城堡序列位于两个你控制的城堡之间，则这个序列可能被两次计算，一次作为从第一个你控制的城堡出发至第二个，一次作为从第二个返回至第一个。尽管如此，重复计算在此算法中的影响有限，因为只有少数情况会发生这种重叠，并且最终我们只关心最大可以摧毁的敌人城堡数量。如果要优化算法以避免重复计算，可以考虑使用额外的数据结构记录已检查的路径或使用动态规划方法优化。