最多可以摧毁的敌人城堡数目
难度:
标签:
题目描述
You are given a 0-indexed integer array forts of length n representing the positions of several forts. forts[i] can be -1, 0, or 1 where:
-1represents there is no fort at theithposition.0indicates there is an enemy fort at theithposition.1indicates the fort at theiththe position is under your command.
Now you have decided to move your army from one of your forts at position i to an empty position j such that:
0 <= i, j <= n - 1- The army travels over enemy forts only. Formally, for all
kwheremin(i,j) < k < max(i,j),forts[k] == 0.
While moving the army, all the enemy forts that come in the way are captured.
Return the maximum number of enemy forts that can be captured. In case it is impossible to move your army, or you do not have any fort under your command, return 0.
Example 1:
Input: forts = [1,0,0,-1,0,0,0,0,1] Output: 4 Explanation: - Moving the army from position 0 to position 3 captures 2 enemy forts, at 1 and 2. - Moving the army from position 8 to position 3 captures 4 enemy forts. Since 4 is the maximum number of enemy forts that can be captured, we return 4.
Example 2:
Input: forts = [0,0,1,-1] Output: 0 Explanation: Since no enemy fort can be captured, 0 is returned.
Constraints:
1 <= forts.length <= 1000-1 <= forts[i] <= 1
代码结果
运行时间: 20 ms, 内存: 16.6 MB
/*
* 思路：
* 使用Java Stream处理数据。
* 首先找到所有你控制的城堡的位置，然后分别计算向左和向右延伸时摧毁的敌人城堡数目。
* 最后返回最大值。
*/
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Solution {
public int captureForts(int[] forts) {
return IntStream.range(0, forts.length)
.filter(i -> forts[i] == 1)
.map(i -> {
int leftDestroyed = (int) IntStream.range(0, i)
.map(j -> i - 1 - j)
.takeWhile(j -> forts[j] == 0)
.count();
int rightDestroyed = (int) IntStream.range(i + 1, forts.length)
.takeWhile(j -> forts[j] == 0)
.count();
return Math.max(leftDestroyed, rightDestroyed);
})
.max()
.orElse(0);
}
}
解释
方法:
这个题解的主要思路是遍历数组 `forts`，寻找从你控制的城堡（值为1）到空位（值为-1），或从空位到你控制的城堡的路径上最多可以摧毁的敌人城堡（值为0）。具体方法是，当遇到你控制的城堡或空位时，开始向后寻找连续的敌人城堡，直到遇到另一个空位或你控制的城堡。如果这段连续敌人城堡的终点是空位或你控制的城堡，则计算这段路径上敌人城堡的数量，并更新最大值。这种方法确保了每个可能的路径都被检查，从而找到最大的可以摧毁的敌人城堡数。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到，算法会在找到连续敌人城堡后计算数量，但未明确是否考虑了连续城堡在数组末尾且未遇到-1或1时的情况，请问如何处理这类边界情况？
▷🦆
在题解算法中，为何在检查完一个可能的路径后需要将索引i回退一步？
▷🦆
题解中提到从你控制的城堡或空位开始寻找，这种起始点的选择对算法效率有何影响？是否存在重复计算路径的风险？
▷