给定一个整数数组 forts
表示城堡,其中 -1 表示无城堡,0 表示敌人城堡,1 表示你控制的城堡。要求找到一种策略,将你的军队从一个你控制的城堡位置移动到一个空的位置,期间只经过敌人的城堡,求最大摧毁敌人城堡的数量。
我们可以通过遍历数组 forts
来解决这个问题。具体步骤如下:
初始化变量 pre
为 -1,用于记录上一个你控制的城堡的位置,以及变量 ans
为 0,用于记录最大摧毁敌人城堡数量。
遍历数组 forts
,对于每个城堡位置:
forts[i] == 1
),则执行以下操作:
pre
不等于 -1,说明之前已经有你控制的城堡,计算当前城堡与上一个你控制的城堡之间的空位数量,即 i - pre - 1
,并将其与 ans
比较,取较大值更新 ans
。pre
更新为当前城堡的位置,以便下次计算空位数量。返回 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;
}
};
通过遍历数组一次,计算了最大摧毁敌人城堡的数量,时间复杂度为 O(n),其中 n 为数组长度。