スライディングウィンドウアルゴリズム

スライディングウィンドウアルゴリズムとは指定した範囲内のデータを少しずつずらしながら処理を行う手法。以下のような用途がある

配列内の部分配列の中で最大の和を求める
文字列のパターン検索。指定サイズの部分文字列が特定の条件を満たしているか

ChatGPTに書いてもらったサンプルコード。配列内のウィンドウ内の最大値を見つけている。時間計算量はO(n)。

def max_sliding_window(nums, k)
  return [] if nums.empty? || k == 0

  result = []
  deque = []

  nums.each_with_index do |num, i|
    # デックの先頭をウィンドウ外の要素から削除
    deque.shift if !deque.empty? && deque[0] < i - k + 1

    # デックの末尾から現在の要素より小さい要素を削除
    while !deque.empty? && nums[deque[-1]] < num
      deque.pop
    end

    # 現在のインデックスをデックに追加
    deque.push(i)

    # ウィンドウが形成されたら結果に最大値を追加
    result << nums[deque[0]] if i >= k - 1
  end

  result
end

# 使用例
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
puts "配列: #{nums}"
puts "ウィンドウサイズ: #{k}"
puts "結果: #{max_sliding_window(nums, k)}"

# 実行結果
# 配列: [1, 3, -1, -3, 5, 3, 6, 7]
# ウィンドウサイズ: 3
# 結果: [3, 3, 5, 5, 6, 7]

参考

https://tomokilab.com/sliding-window-python/