プログラミングコンテストチャレンジブック 4-4 その1

4-4 「厳選! 頻出テクニック(2)」からです。

• スタックの利用
  • Largest Rectangle in a Histgram - ヒストグラムから最大面積の長方形を探す
• デック(Deque)の利用
  • スライド最小値 - 数列の最小移動曲線みたいなものを求める(bi が ai から ai+k-1 までの最小値になる)
    • Deque に格納されている値を先頭から xi とした時 xi < xi+1 かつ axi < axi+1 が成り立つようにしながらインデックスを増やしていき先頭のインデックスを j として bi = aj