難しい 1件解決済み 正答率100.0%

Sliding Window Maximum

Report the maximum of every window of k numbers.

このチャレンジで学べること

  • ウィンドウの候補を deque で管理する
  • ウィンドウから外れた値を取り除く
  • O(n) ですべてのウィンドウの最大値を得る

問題

Slide a window of size k across the list one step at a time and report the maximum inside each window. A deque keeps this O(n).

Implement window_maximums(numbers, k).

Input

numbers: The list of integers. k: The window size.

Output

Return the maximum of each window, left to right.

制約

1 ≤ k ≤ length ≤ 200,000

例

例 1
入力:
numbers = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3

期待される出力:
expected = [3, 3, 5, 5, 6, 7]
入力:
std::vector<long long> numbers = {1, 3, -1, -3, 5, 3, 6, 7};
long long k = 3;

期待される出力:
std::vector<long long> expected = {3, 3, 5, 5, 6, 7};
入力:
long[] numbers = new long[] {1, 3, -1, -3, 5, 3, 6, 7};
long k = 3;

期待される出力:
long[] expected = new long[] {3, 3, 5, 5, 6, 7};

解説

Windows [1,3,-1], [3,-1,-3], [-1,-3,5], … have maxima 3, 3, 5, 5, 6, 7.

例 2
入力:
numbers = [4, 2]
k = 1

期待される出力:
expected = [4, 2]
入力:
std::vector<long long> numbers = {4, 2};
long long k = 1;

期待される出力:
std::vector<long long> expected = {4, 2};
入力:
long[] numbers = new long[] {4, 2};
long k = 1;

期待される出力:
long[] expected = new long[] {4, 2};

解説

Windows of one element are the elements themselves: [4, 2].

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

最大値は窓から外れると消えるので、値とインデックスの両方で更新できる構造が必要です。

ヒント 2

候補のインデックスを値の降順で保ち、現在の窓外のものは捨てます。

ヒント 3

最初の完成した窓とサイズ1の窓に注意し、各答えは必ず完成した窓に対応させます。

目安の計算量

時間 O(n)、追加メモリ O(k)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

# コーダー 言語 時間 メモリ AI 評価 解答
1 ННикита Python 824 ms - 5/5 コードを見る

他の人の解答から学ぶ

コミュニティの解答

ネタバレ注意:下に1件の全解答あり まずは自分で挑戦してみましょう。他の開発者のコードやAIレビューも見ることができます。 サインインして課題を解くと議論に参加できます。