スライド最小値・最大値
スライド最小値・最大値は、最大値・最小値の取得ができるキューのようなデータ構造。
構造
Deque（両端キュー）に、値を入れていく。
このとき、
スライド最小値の場合、単調非減少となるようにする。
スライド最大値の場合、単調非増加となるようにする。
要素を追加するとき（末尾のみ）
計算量：ならし$ O(1)、最悪$ O(n)
スライド最小値の場合
ある値$ xを追加するとき、Dequeの末尾の要素を削除することにより、$ xより大きい要素をすべて取り除く。
次に、$ xをDequeの末尾に追加する。
スライド最大値の場合
ある値$ xを追加するとき、Dequeの末尾の要素を削除することにより、$ xより小さい要素をすべて取り除く。
次に、$ xをDequeの末尾に追加する。
要素を削除するとき（先頭のみ）
計算量：$ O(1)
Dequeの先頭の要素を削除するだけ。
Dequeの中身には単調性があるため、次の要素が次の最小値・最大値となる。
最小値・最大値を取得するとき
計算量：$ O(1)
Dequeの先頭の要素は常に最小値・最大値となっている。
補足
Dequeに入れる要素を(値, インデックス)とすることにより、インデックスが$ kより小さい要素をすべて削除するといった操作も可能。
Dequeの中身はインデックスについて単調増加となる。