単調スタック

単調スタックは、要素を増加順または減少順に保ち、その順序を崩す要素が来たら取り出していくスタックです。取り出すたびに、その値にとっての次に大きい（小さい）要素がわかります。Daily Temperatures が代表的な例です。

4 章 35 問と、比較的短い問題集です。基本の単調スタックから Largest Rectangle in Histogram とその仲間へ進み、寄与法ですべての部分配列にわたる和を求め、最後は辞書順最小の答えを組み立てる問題で締めくくります。考え方は知っているのに、ヒストグラムの問題で手が止まる人に向いています。