典型タグ

単調stack・queueによる支配候補の削除

順序に走査し、新しい要素に支配された候補を二度と必要にならないことを示して一度だけ削除する。

この典型を扱う単元: 支配関係から不要な候補を単調stack・queueで削る

検索別名: monotonic queue、monotonic stack、単調キュー、単調スタック

未知問からこの典型を見つける手掛かり

扱う対象
  • 候補
  • 次に大きい
  • 次に小さい
  • 窓
  • 高さ
使う手掛かり
  • pop
  • 各要素を一度
  • 後ろから削除
  • 支配
  • 次に大きい
保つ不変量
  • stack
  • 不要になった候補
  • 二度と戻らない
  • 単調
求めるもの
  • nearest greater
  • 区間最大
  • 各prefix
  • 次の要素
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: 更新可能な最小十分要約

    関連する典型

      学習成果と学習単位

      代表問題

      この典型の考え方を具体的な問題で確かめるための入口です。

      関連問題

      この典型が主タグまたは補助タグとして付いている問題です。