🦁

LeetCode 1493. Longest Subarray - スライディングウィンドウを使ってO(n)計算量に収める

2025/08/24に公開

LeetCode

tech

1493. Longest Subarray of 1's After Deleting One Element

Intution

配列から一つの要素を削除して、1だけを含む一番長い配列の長さを計算する。

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
index = 4 の0を削除する。

ブルートフォースでは解けそうではあるので解いてみる
- ループごとに自分の要素を削除した配列を作ってブルートフォースで解いた。
  - Time Limit Exceededなので別の解き方がやはりあるはず。
    - nums.each.width_indexのO(n)ループ内に、nums.select.with_indexのO(n)ループ内に、new_numsのO(n)ループがあるため、O(n^3)の計算量となってしまう。

def longest_subarray(nums)    
    result = 0
    nums.each.with_index do |n, index| 
      new_nums =   nums.select.with_index do |_n, index2|
                     index2 != index
                    end

            count = 0
            new_nums.each do |n| 
            if n == 1
              count=count+1
              result = count if count > result
            else
              count = 0
            end
        end
    end
    return result
end

Approach

スライディングウィンドウ
- 要素の削除ではなく、ウィンドウに含まれる0の数が1つ以下の配列の条件に従ってウィンドウ範囲を絞って処理をするようにする。
- zero_countはウィンドウ配列内に含まれる0の数を指す。zero_countが1つ以下になるように、left_indexを指定する。

テストケース①

Input: nums = [1,1,0,1]
[1,1,0,1]
 L
 R

を例にステップで記載する。

i = 0 (nums[0] は 1): 何もせずスキップ。left_index = 0。

[1,1,0,1]
 L
 R
=> longest_window(right_index - left_index): 0

i = 1 (nums[1] は 1): 何もせずスキップ。left_index = 0。

[1,1,0,1]
 L
   R
=> longest_window(right_index - left_index): 1

i = 2 (nums[2] は 0): zero_count = 1で、left_index = 0のまま。

[1,1,0,1]
 L
     R
=> longest_window(right_index - left_index): 2

i = 3 (nums[3] は 1): 何もせずスキップ。left_index = 0のまま。

[1,1,0,1]
 L
       R
=> longest_window(right_index - left_index): 3

テストケース②

Input: nums = [0,1,1,1,0,1,1,0,1]

の場合では、i = 6 (nums[6] は 1):の場合に最大のウィンドウサイズとなる

[0,1,1,1,0,1,1,0,1]
   L
             R
=> zero_count = 1
=> longest_window(right_index - left_index): 6

ruby

rubyで再実装しました。

# @param {Integer[]} nums
# @return {Integer}
def longest_subarray(nums)
    zerocount = 0
    max_length = 0
    left_index = 0

    nums.each.with_index do |num, right_index|
      zerocount = zerocount + 1 if num == 0

      while zerocount > 1
        zerocount = zerocount - 1 if nums[left_index] == 0
        left_index = left_index + 1
      end
      max_length = [max_length, right_index - left_index].max
    end
    return longest
end

以下、他の言語でスライディングウィンドウを実装した。

python

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        zero_count_in_window = 0
        start_index = 0
        max_length = 0

        for end_index in range(len(nums)):
            num = nums[end_index]
            if num == 0:
              zero_count_in_window += 1
            
            while zero_count_in_window > 1:
                if nums[start_index] == 0:
                  zero_in_window -= 1
                start_index += 1
            
            max_length = max(max_length, end_index - start_index)
        return max_length

typescript

function longestSubarray(nums: number[]): number {
  let zero_count_in_window: number = 0
  let start_index: number = 0
  let max_length: number = 0

  for(let end_index = 0; end_index < nums.length; end_index++){
    if(nums[end_index] == 0) zero_count_in_window++

    while(zero_count_in_window > 1){ // ウィンドウ内の0を1以下になるようにwindow幅を調整
      if (nums[start_index] == 0){
        zero_count_in_window--
      }
      start_index++
    }
    max_length = Math.max(max_length, end_index - start_index)
  }  
  return max_length
};

golang

func longestSubarray(nums []int) int {
    var zero_count_in_window int = 0
    var start_index int = 0
    var max_length int = 0

    for end_index := 0; end_index < len(nums); end_index++ {
        if nums[end_index] == 0 {
            zero_count_in_window++
        }

        for zero_count_in_window > 1 {
            if nums[start_index] == 0 {
                zero_count_in_window--
            }
            start_index++
        }
        max_length = max(max_length, end_index-start_index)
    }
    return max_length
}

学習のポイント

スライディングウィンドウとは特定の条件で作ったサブ配列を見つけるアルゴリズムのこと
ブルートフォースで0を削除した配列の全パターンを作るのではなく、スライディングウィンドウの条件で0が1以下のサブ配列を作ることで解くことができる。
スライディングウィンドウを使うことが計算量をO(n)にできる。

1493. Longest Subarray of 1's After Deleting One Element

Intution

Approach

学習のポイント

Discussion