両端キューで幅 k の窓ごとの最大値を並べる

スライディングウィンドウ問題 104

毎分の数の並びで、直近 k 分ごとの最大値を全部並べます。値が下がっていく順に添字を両端キューに持ち、窓の外と負けた値を捨てていく、スライディングウィンドウと単調キューの練習です。

海外で定番の問題リスト 4 本には入っていません

問題

あるサイトに 1 分ごとに来た人の数の増減を、整数の並び nums で受け取ります。幅 k の窓 (続いた k 分) を左端から 1 分ずつ右へずらし、窓ごとの最大値を左の窓から順に並べた並びを返す関数を書いてください。

窓は nums[0] から nums[k - 1] が最初で、nums[n - k] から nums[n - 1] が最後です。返す並びの長さは n - k + 1 です
nums の長さ n は 1 以上 100000 以下で、値は -10000 以上 10000 以下です
k は 1 以上 n 以下です

入力と出力の例

例 1

最初の 3 つの窓には 12 が入っています。12 が窓から出たあとは、8 の入った 2 つの窓が続きます。

nums = [4, 2, 12, 3, 8, 1, 6] k = 3

[12, 12, 12, 8, 8]

例 2

幅 1 の窓は値 1 つだけなので、並びがそのまま答えです。

nums = [5, -1, 3] k = 1

[5, -1, 3]

例 3

下がっていく並びでは、窓の左端がいつも最大です。最後の窓だけ、右から入った 6 が最大になります。

nums = [9, 7, 5, 3, 6] k = 2

[9, 7, 5, 6]

面接での聞かれ方

面接では、計算量の条件つきで渡されることがよくあります。

「幅 k の窓をずらしながら、各窓の最大値を返してください。O(n) でできますか？」
「k が 1 のときと、k が n のときは？」と、端の場合を聞かれることがあります
ヒープで O(n log n) の答えを言ったあとに、「もっと速くなりませんか？」と詰められることもあります

窓ごとに最大を探し直す書き方、ヒープの書き方、両端キューの書き方の 3 段で話せると、考えの筋が伝わります。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

素直に書くなら、窓ごとに k 個の値を見て最大を探します。窓が n - k + 1 個あるので O(n × k) です。n も k も 5 万ほどなら 25 億回になり、遅すぎます。

段 2

最大を出し入れするならヒープも使えます。値と添字の組をヒープに入れ、いちばん上が窓の外なら捨ててから最大を読みます。O(n log n) で間に合いますが、もう一段縮められます。

段 3

大事な見方は、「右から大きい値が入ったら、それより左の小さい値は二度と最大にならない」ことです。大きい値の方があとまで窓に残るからです。そこで、最大になる見込みのある添字だけを、値が下がっていく順にキューに持ちます。新しい値が入るとき、キューの右の端の値がそれ以下なら捨て続けてから、右の端に足します。

段 4

キューの左の端が、いまの窓の最大です。ただし、左の端の添字が窓の外 (いまの位置 i から見て i - k 以下) に出ていたら、左から捨てます。左右の両方から捨てるので、両端から出し入れできる両端キューを使います。値ではなく添字を持つのは、窓の外に出たかを確かめるためです。

解答

Python

from collections import deque


def window_max(nums, k):
    q = deque()
    out = []
    for i, x in enumerate(nums):
        while q:
            if nums[q[-1]] > x:
                break
            q.pop()
        q.append(i)
        if q[0] <= i - k:
            q.popleft()
        if i >= k - 1:
            m = nums[q[0]]
            out.append(m)
    return out

JavaScript

function windowMax(
  nums,
  k
) {
  const q = [];
  let head = 0;
  const out = [];
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    const x = nums[i];
    while (
      q.length > head &&
      nums[q[q.length - 1]] <= x
    ) {
      q.pop();
    }
    q.push(i);
    if (q[head] <= i - k) {
      head++;
    }
    if (i >= k - 1) {
      out.push(nums[q[head]]);
    }
  }
  return out;
}

Go

func windowMax(
	nums []int,
	k int,
) []int {
	q := []int{}
	out := []int{}
	for i, x := range nums {
		for len(q) > 0 &&
			nums[q[len(q)-1]] <= x {
			q = q[:len(q)-1]
		}
		q = append(q, i)
		if q[0] <= i-k {
			q = q[1:]
		}
		if i >= k-1 {
			m := nums[q[0]]
			out = append(out, m)
		}
	}
	return out
}

q には添字が、指す値が下がっていく順に入っています。右の端の値が新しい値 x 以下なら、もう最大にならないので捨てます。左の端が窓の外に出ていたら捨てます。1 回に出るのは多くて 1 つで足ります。添字は 1 つずつ増えるので、窓から出るのも 1 回に 1 つだからです。JavaScript には両端キューが無いので、配列と左の端の位置 head で代わりにし、左から捨てるときは head を進めます。

計算量

時間は O(n) です。どの添字も、キューに入るのが 1 回、出るのが多くて 1 回です。右から捨て続ける繰り返しも、全体で n 回を越えません
使う記憶は O(k) です。キューには窓の中の添字しか残りません。答えの並びの n - k + 1 個は数えていません。ただし JavaScript の解答は、head より前の使い終わった添字を配列から消さないので、配列は O(n) まで伸びます。O(k) に収めたいときは、head が配列の半分を越えたら前を切り詰めます
段 1 の窓ごとに探し直す書き方は O(n × k)、段 2 のヒープは O(n log n) です

よくある間違い

キューに添字ではなく値を入れる。同じ値がいくつもあると、どれが窓から出たのか分からなくなります。添字を入れ、値は nums から読みます
右から捨てる条件を < にして、同じ値を残す。 答えは変わりませんが、同じ値が続く並びで、キューが窓の幅まで伸びます。<= で捨てても、新しい方が長く残るので困りません
左の端が窓の外に出たかを確かめ忘れる。窓の外の古い最大を答えに入れます。例 1 の 4 つ目の窓 [3, 8, 1] で、外に出た 12 を返してしまいます
最初の窓がそろう前から答えに足す。 i >= k - 1 になるまでは足しません。足すと、答えの並びが k - 1 個長くなります

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def window_max(nums: list[int], k: int) -> list[int]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(window_max([4, 2, 12, 3, 8, 1, 6], 3))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します