付費限定文章

滑動窗口應用: 刪掉一個元素之後，最長有幾個連續為1的子陣列_Leetcode 精選75題

marianne bos on Unsplash

題目敘述

題目會給定一個二元陣列nums(也就是說，陣列元素只有0,1這兩種情況)。

我們必須從裡面選擇一個元素刪除之後，請問連續為1的最長子陣列的長度是多少?

題目的原文敘述

測試範例

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

刪除0，陣列變成[1,1,1]連續為1的最長子陣列長度為3​

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

刪除中間的那個0，陣列變成[1,1,1,1,1]連續為1的最長子陣列長度為5

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.
選擇刪除最左邊或最右邊的1，陣列變成[1,1]連續為1的最長子陣列長度為2

演算法

關鍵在於題目的要求是子陣列，而不是子序列。

子陣列一定要求必須連續。因此，最適合的演算法框架為滑動窗口sliding window。

題目要求我們必須從裡面選擇一個元素刪除。

接著建立一個起始點從0開始的滑動窗口，依序從左向右滑動。

遇到第一個0，就先設定為被刪除的元素。

遇到第二個0，就收縮左邊界，直到離開第一個0為止。

每次窗口滑動時，動態更新最長子陣列的長度。

程式碼

class Solution:
  def longestSubarray(self, nums: List[int]) -> int:
    ans = 0
    count0 = 0

    l = 0
    for r, num in enumerate(nums):
      
      if num == 0:
        # delete zero
        count0 += 1
      
      while count0 == 2:
        # meet two 0s, update left boundary  
        if nums[l] == 0:
          count0 -= 1
        l += 1

      ans = max(ans, r - l)

    return ans

複雜度分析