Easy

题目描述

给你一个下标从 0 开始的整数数组 forts，长度为 n，表示一些城堡的位置。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，捕获位置 1 和位置 2 的敌方城堡，共 2 个。
- 将军队从位置 8 移动到位置 3，捕获位置 4、5、6、7 的敌方城堡，共 4 个。
4 是最多可以捕获的敌方城堡数目，所以返回 4。

示例 2：

输入：forts = [0,0,1,-1]
输出：0
解释：由于无法捕获敌方城堡，所以返回 0。

提示：

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

解题思路

这道题的关键在于理解移动规则：军队必须从己方城堡（值为1）移动到空位置（值为-1），且中间经过的所有位置都必须是敌方城堡（值为0）。

解题思路：

我们需要找到所有可能的移动路径，每条路径的起点是己方城堡（1），终点是空位置（-1），中间全部是敌方城堡（0）。

双指针方法：

  1. 使用两个指针遍历数组，寻找连续的模式：1...0...0...-1 或 -1...0...0...1
  2. 对于每个非零位置（1或-1），向两个方向扩展，寻找另一个非零位置
  3. 如果找到的两个非零位置恰好是1和-1的组合，则中间的0的个数就是可以捕获的敌方城堡数

优化思路： 遍历数组，当遇到非零元素时，记录位置和值。如果当前非零元素与前一个非零元素的值不同（一个是1，一个是-1），则它们之间的距离减1就是可捕获的敌方城堡数。

这种方法只需要一次遍历，时间复杂度为O(n)，空间复杂度为O(1)。

代码实现

class Solution {
public:
    int captureForts(vector<int>& forts) {
        int maxCapture = 0;
        int prev = -1; // 记录前一个非零位置
        
        for (int i = 0; i < forts.size(); i++) {
            if (forts[i] != 0) {
                if (prev != -1 && forts[prev] != forts[i]) {
                    // 前一个非零位置和当前位置值不同（一个是1，一个是-1）
                    maxCapture = max(maxCapture, i - prev - 1);
                }
                prev = i;
            }
        }
        
        return maxCapture;
    }
};

class Solution:
    def captureForts(self, forts: List[int]) -> int:
        max_capture = 0
        prev = -1  # 记录前一个非零位置
        
        for i in range(len(forts)):
            if forts[i] != 0:
                if prev != -1 and forts[prev] != forts[i]:
                    # 前一个非零位置和当前位置值不同（一个是1，一个是-1）
                    max_capture = max(max_capture, i - prev - 1)
                prev = i
        
        return max_capture

public class Solution {
    public int CaptureForts(int[] forts) {
        int maxCapture = 0;
        int prev = -1; // 记录前一个非零位置
        
        for (int i = 0; i < forts.Length; i++) {
            if (forts[i] != 0) {
                if (prev != -1 && forts[prev] != forts[i]) {
                    // 前一个非零位置和当前位置值不同（一个是1，一个是-1）
                    maxCapture = Math.Max(maxCapture, i - prev - 1);
                }
                prev = i;
            }
        }
        
        return maxCapture;
    }
}

var captureForts = function(forts) {
    let maxCapture = 0;
    let prev = -1; // 记录前一个非零位置
    
    for (let i = 0; i < forts.length; i++) {
        if (forts[i] !== 0) {
            if (prev !== -1 && forts[prev] !== forts[i]) {
                // 前一个非零位置和当前位置值不同（一个是1，一个是-1）
                maxCapture = Math.max(maxCapture, i - prev - 1);
            }
            prev = i;
        }
    }
    
    return maxCapture;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

相关题目