単調スタックは候補を値の順に保つので、新しい要素1つで、前の複数の問いを解決できます。次に大きい値を探す走査では、未解決の小さい値は、現在の値が最初の答えになったときに取り除かれます。前の小さい値を探す走査では、現在の要素のほうが近く、後の探索にとって少なくとも同じくらい役立つので、大きいか等しい候補は取り除かれます。
各インデックスは1回だけ入って1回だけ出ます。そのため、個々のループの反復で多くの要素をポップしても、全体の処理は線形になります。この数え方を、大きい値、前の小さい値、圧縮した需要の区間、スカイラインの長方形、ウィンドウの最大値に使います。コードを書く前に、等しい値でポップするかどうかを決めてください。両端キューでは先頭での期限切れが加わり、スカイラインのスタックでは、より低い実際の列に出会わない候補を閉じるために最後に番兵が必要です。
課題では厳密に大きい値が必要なので、2つ目の4が来たときも、4の荷重は2つとも未解決のままです。続く2はより小さいので、これもスタックに残ります。7が来ると、3つの位置がすべて解決します。どれもそれ以前に条件を満たす後続の値に出会っておらず、出会っていればすでにスタックから出ていたはずです。最後の5は7を解決できず、どちらにもそれより後の大きい荷重がないので、既定の答えは-1のままです。7によって1回の反復で3回のポップが起きますが、それらのインデックスが再びポップされることはありません。走査全体で、プッシュはn回だけ、ポップは多くてもn回です。