【要約】単調スタックを図解｜右側で最初に大きい値をO(n)で探す [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
開発者が配列内の各要素について、その右側に存在する「自分より大きい最初の値」を特定しようとする際、計算量の増大という問題に直面する。単純な実装では、各要素から右方向へ順次探索を行うため、要素数が増えるにつれて比較回数が急増する。具体的には以下の課題がある。
- ・素朴な実装では、各位置から右側を走査するため、計算量がO(n^2)に達する。
- ・値が降順に並ぶ配列では、探索が最後まで続行されるため、最悪のケースが頻発する。
- ・大規模なデータセットにおいて、この計算量の増大は処理遅延の致命的な要因となる。
// Approach
この課題に対し、未解決のインデックスを管理する「単調スタック」を用いることで、走査回数を最小限に抑えるアプローチを採用する。配列を左から右へ一度だけ走査し、現在値がスタック内の値より大きい場合に答えを確定させる。具体的な手順は以下の通りである。
- ・スタックには値そのものではなく、未解決の「位置（インデックス）」を保存する。
- ・現在値がスタックの最上部の値より大きい場合、whileループを用いて条件を満たす間、スタックから要素を取り出し続ける。
- ・取り出した位置の答えを、現在値で確定させる。
- ・最後に、現在の位置を未解決としてスタックに追加する。
// Result
単調スタックの導入により、計算量をO(n^2)からO(n)へと劇的に削減することに成功した。各要素はスタックへの追加と取り出しが最大1回ずつであるため、線形時間での処理が可能となる。得られた成果は以下の通りである。
- ・時間計算量：O(n)を実現。
- ・空間計算量：O(n)（答えの配列とスタックの保持のため）。
- ・具体的な動作例：[4, 2, 7, 3, 6, 8] の入力に対し、[7, 7, 8, 6, 8, None] を正しく出力する。
Senior Engineer Insight
> アルゴリズムの選択がシステム全体のレイテンシに直結することを再認識させる内容だ。特にストリーム処理や時系列データの解析において、O(n^2)とO(n)の差は、単なる速度差ではなく、システムの生存可否を分ける。実装時には、値ではなくインデックスをスタックに積む点や、whileによる連続確定のロジックを誤らないよう注意が必要だ。計算量だけでなく、メモリ使用量も考慮した設計が求められる。