Question

2511. Maximum Enemy Forts That Can Be Captured

中文文档

Description

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:

• -1 represents there is no fort at the ith position.
• 0 indicates there is an enemy fort at the ith position.
• 1 indicates the fort at the ith the 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 k where min(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

Solutions

Solution 1

class Solution:
  def captureForts(self, forts: List[int]) -> int:
    n = len(forts)
    i = ans = 0
    while i < n:
      j = i + 1
      if forts[i]:
        while j < n and forts[j] == 0:
          j += 1
        if j < n and forts[i] + forts[j] == 0:
          ans = max(ans, j - i - 1)
      i = j
    return ans

class Solution {
  public int captureForts(int[] forts) {
    int n = forts.length;
    int ans = 0, i = 0;
    while (i < n) {
      int j = i + 1;
      if (forts[i] != 0) {
        while (j < n && forts[j] == 0) {
          ++j;
        }
        if (j < n && forts[i] + forts[j] == 0) {
          ans = Math.max(ans, j - i - 1);
        }
      }
      i = j;
    }
    return ans;
  }
}

class Solution {
public:
  int captureForts(vector<int>& forts) {
    int n = forts.size();
    int ans = 0, i = 0;
    while (i < n) {
      int j = i + 1;
      if (forts[i] != 0) {
        while (j < n && forts[j] == 0) {
          ++j;
        }
        if (j < n && forts[i] + forts[j] == 0) {
          ans = max(ans, j - i - 1);
        }
      }
      i = j;
    }
    return ans;
  }
};

func captureForts(forts []int) (ans int) {
  n := len(forts)
  i := 0
  for i < n {
    j := i + 1
    if forts[i] != 0 {
      for j < n && forts[j] == 0 {
        j++
      }
      if j < n && forts[i]+forts[j] == 0 {
        ans = max(ans, j-i-1)
      }
    }
    i = j
  }
  return
}

function captureForts(forts: number[]): number {
  const n = forts.length;
  let ans = 0;
  let i = 0;
  while (i < n) {
    let j = i + 1;
    if (forts[i] !== 0) {
      while (j < n && forts[j] === 0) {
        j++;
      }
      if (j < n && forts[i] + forts[j] === 0) {
        ans = Math.max(ans, j - i - 1);
      }
    }
    i = j;
  }
  return ans;
}

impl Solution {
  pub fn capture_forts(forts: Vec<i32>) -> i32 {
    let n = forts.len();
    let mut ans = 0;
    let mut i = 0;
    while i < n {
      let mut j = i + 1;
      if forts[i] != 0 {
        while j < n && forts[j] == 0 {
          j += 1;
        }
        if j < n && forts[i] + forts[j] == 0 {
          ans = ans.max(j - i - 1);
        }
      }
      i = j;
    }
    ans as i32
  }
}

Solution 2

impl Solution {
  pub fn capture_forts(forts: Vec<i32>) -> i32 {
    let mut ans = 0;
    let mut i = 0;

    while
      let Some((idx, &value)) = forts
        .iter()
        .enumerate()
        .skip(i)
        .find(|&(_, &x)| x != 0)
    {
      if
        let Some((jdx, _)) = forts
          .iter()
          .enumerate()
          .skip(idx + 1)
          .find(|&(_, &x)| x != 0)
      {
        if value + forts[jdx] == 0 {
          ans = ans.max(jdx - idx - 1);
        }
      }
      i = idx + 1;
    }

    ans as i32
  }
}