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

题目描述

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

解法一：一次遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


func max(nums ...int) int {
    res := nums[0]
    for _, num := range nums {
        if num > res {
            res = num
        }
    }
    return res
}

func captureForts(forts []int) int {
    n := len(forts)
    pL, pR := 1000, -1000
    ans := 0
    for i := 0; i < n; i++ {
        j := n - 1 - i
        switch forts[i] {
        case -1:
            pL = i
        case 1:
            ans = max(ans, i-pL-1)
            pL = 1000
        }
        switch forts[j] {
        case -1:
            pR = j
        case 1:
            ans = max(ans, pR-j-1)
            pR = -1000
        }
    }
    return ans
}

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func captureForts(forts []int) int {
    ans, pre := 0, -1
    for i, fort := range forts {
        if fort == -1 || fort == 1 {
            if pre >= 0 && forts[pre] != fort {
                ans = max(ans, i - pre - 1)
            }
            pre = i
        }
    }
    return ans
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}