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

难度: 简单

来源: 每日一题 2023.09.02

---

给你一个长度为 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

class Solution {
    public int captureForts(int[] forts) {

    }
}

分析与题解

---

• 模拟法

  这个题目理解了题意就整体比较简单了, 这个题目的简化后, 实际上求数组中 所有 -1 和 1 区间的最大间距

  这种区间问题, 我们需要知道何时进入区间, 何时离开区间.

  所以我们设置一个变量 startNum 用于记录进入区间的值是 1 还是 -1 .

  int startNum = 0;
  

  进入区间的条件就是 当前数值不为 0, 并且 startNum 为 0.

  if (startNum == 0 && item != 0) {
      // 进入区间
      startNum = item;
  } 
  

  那么如何停止区间和进入一下区间呢? 这时候我们需要判断 当前已经在区间内, 并且 当前数值不为0.

  • 如果 startNum 与当前数值相等, 那么就进入重置, 进入下一个区间. 比如 [1, 0, 0, 1] 这个区间是不符合题意的, 所以我们需要进行重置.

  • 如果 startNum 与当前数值不相等, 那么就进入停止. 判断区间长度, 并且重置进入下一个区间, 比如 [1, 0, 0, -1].

  if (startNum != 0 && item != 0) {
      // 停止区间 或 重置区间
      if (startNum != item) {
          // 停止区间
          result = Math.max(result, tempSum);
      }
      startNum = item;
      tempSum = 0;
  }
  

  再就是区间的长度的统计, 就是当进入区间之后, 当前值为0. 我们就进行数据的统计.

  if(startNum != 0 && item == 0) {
      // 进入区间了, 所以遇到0要记录
      tempSum++;
  }
  

  整体逻辑代码如下所示.

  class Solution {
      public int captureForts(int[] forts) {
          // 分析题目可知
          // 我们要判别的条件是 -1 和 1 之间的夹值
          // 见到 1 或者 -1 启动, 进入区间
          // 那么操作就有 区间 之和等于 0,停止 大于1 或者小于-1 重置
          int result = 0, tempSum = 0, startNum = 0;
          for(int i = 0; i < forts.length; i++) {
              int item = forts[i];
              if (startNum == 0 && item != 0) {
                  // 进入区间
                  startNum = item;
              } else if (startNum != 0 && item != 0) {
                  // 停止区间 或 重置区间
                  if (startNum != item) {
                      // 停止区间
                      result = Math.max(result, tempSum);
                  }
                  startNum = item;
                  tempSum = 0;
              } else if(startNum != 0 && item == 0) {
                  // 进入区间了, 所以遇到0要记录
                  tempSum++;
              }
          }
          return result;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 一次遍历循环, 时间复杂度与数组长度相关.
  • 空间复杂度: O(1), 常量级别的空间复杂度.

  结果如下所示.