LeetCode每日一题 2511. 最多可以摧毁的敌人城堡数目

题解：摧毁敌人城堡

给定一个整数数组 forts 表示城堡，其中 -1 表示无城堡，0 表示敌人城堡，1 表示你控制的城堡。要求找到一种策略，将你的军队从一个你控制的城堡位置移动到一个空的位置，期间只经过敌人的城堡，求最大摧毁敌人城堡的数量。

解题思路

我们可以通过遍历数组 forts 来解决这个问题。具体步骤如下：

1. 初始化变量 pre 为 -1，用于记录上一个你控制的城堡的位置，以及变量 ans 为 0，用于记录最大摧毁敌人城堡数量。

2. 遍历数组 forts，对于每个城堡位置：

   • 如果该位置为你控制的城堡（forts[i] == 1），则执行以下操作：
     • 如果 pre 不等于 -1，说明之前已经有你控制的城堡，计算当前城堡与上一个你控制的城堡之间的空位数量，即 i - pre - 1，并将其与 ans 比较，取较大值更新 ans。
     • 将 pre 更新为当前城堡的位置，以便下次计算空位数量。

3. 返回 ans 作为最大摧毁敌人城堡数量。

代码示例

class Solution {
public:
    int captureForts(vector<int>& forts) {
        int n = forts.size();
        int pre = -1, ans = 0;
        
        for (int i = 0; i < n; ++i) {
            if (forts[i] == 1) {
                if (pre != -1) {
                    int temp = i - pre - 1;
                    ans = max(ans, temp);
                }
                pre = i;
            }
        }
        
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

通过遍历数组一次，计算了最大摧毁敌人城堡的数量，时间复杂度为 O(n)，其中 n 为数组长度。