スライド最大（最小）値・ヒストグラム内最大長方形問題を俯瞰する

はじめに

長さ$N$の配列が与えられて，愚直に計算すると$\mathcal{O}(N^2)$かかってしまうところを，デック(deque)やスタックを用いてうまく計算することで$\mathcal{O}(N)$に改善することができる有名問題に次の2つがあります．

1. 配列内の長さ$K ( \leq N)$の区間すべてに対して，その区間内の最大(最小)値を求める （スライド最大(最小)値）
2. $N$個の幅$1$，高さ$H_i$（$0 \leq i < N$)の長方形をこの順に並べてできるヒストグラムに含まれる長方形の面積の最大値を求める (ヒストグラム内最大長方形問題)

この記事ではこの2つのアルゴリズムのポイントと類似点を自分なりの視点で解説します．

1. スライド最大（最小）値

解きたい問題は次のような問題です．

配列内の長さ$K$の区間すべてに対して，その区間内の最大(最小)値を求める

愚直な解法としては，「左端を固定して右方向に$K$個の値を調べて最大値を調べる」を$(N-K+1)$回繰り返す$\mathcal{O}(NK)$($ = \mathcal{O} (N^2)$)の解法や，セグメントツリーのような区間に対する最大(最小)値クエリを$\mathcal{O}(\log N)$で実行するデータ構造を使った$\mathcal{O}(N \log N)$の解法があります．これを視点を変えて走査することで$\mathcal{O}(N)$で計算することができます．

ポイント $K$年制の学校で自分が何年のあいだ番長を務められるか考える

区間に着目するのではなくそれぞれの数字に着目し，固定長$K$の区間が右にスライドしていくなかで，自分が最大値になることができる期間を考えるとします．
考えやすくするために，数値を戦闘力，区間に入るのを入学，区間から出るのを卒業と考えます．留年制度はなく必ず$K$年で卒業します．
この時，次のようなシチュエーションになることが想像できます．

1. 入学時（= 区間の最右に居る時），在校する先輩達の誰よりも強いためいきなり番長（区間内の最大値）になるか，自分より強い先輩が在学している（先輩が引き続き番長を務める）．

• 自分が番長になった場合，自分が番長でいられる期間は，自分より強い後輩が入ってくるまでか，あるいは入ってこないまま学校から卒業して任期を終える．
• 自分が番長でない場合，先輩が卒業するのを待てば，そのあと番長になる可能性がある（のでその時を待つ）．
• 自分より強い先輩の卒業を待つ間に自分より強い後輩が入学してくると，番長になる望みは消える．

このように考えると，年が変わるごとに番長順番待ちキューが図のように変わって行くのをシミュレートして実装できればよさそうです．各個人は，番長順番待ちキューに入る，キューから出るの2回しか動かないため，区間が左から右に走査する全体の計算量は$\mathcal{O}(N)$になります．番長順番待ちキューからでるのは，任期を全うして卒業する時には左から出て，強い後輩が入ってきて後輩に席を譲るときは右からでると考えると，これはまさにdequeで実現できる動作になります．

slide_max_index.py

from collections import deque

def slide_max_index(a, K):
    # max_idx[i]: 区間 [i - K + 1, i] (両側閉区間)における a の最大値を与えるインデックス
    N = len(a)
    max_idx = [0] * N # (長さKに満たない左側領域もついでに計算する)
    deq = deque() # デック．番長順番待ちキューをシミュレートする．インデックスを格納しておく

    for i in range(0,N):
        while len(deq) > 0 and deq[0] <= i - K : deq.popleft() # 卒業する
        while len(deq) > 0 and a[deq[-1]] < a[i] : deq.pop()   # a[i] の入学で 望みがなくなった先輩達が脱落する
        deq.append(i)                                          # 新入生i は常に番長になる望みがある
        max_idx[i] = deq[0]                                    # 番長順番待ちキューの最左が番長
    
    return max_idx

2. ヒストグラム内最大長方形問題

解きたい問題は次のような問題です．

$N$個の幅$1$，高さ$H_i$（$0 \leq i < N$)の長方形をこの順に並べてできるヒストグラムに含まれる長方形の面積の最大値を求める

少し考察が必要ですが，どの長方形を考えた場合にも，最大面積を与える長方形はどこかである$H_i$が天井になっているはずなので，各$i$に対して「$H_i$が天井になるような長方形のうち一番大きいもの」を列挙して，その中から最大面積になるものを選べばいい，という解法になります．

なので，カギとなるアルゴリズムを小問題として言い換えると，次のようになります．

長さ$N$の配列の各点に対して，自分より右にあって最初に自分より小さくなるものの位置を求めたい

これが解ければ右側どこまで伸ばすことができるかがわかり，同じようにして左側どこまで伸ばせるかもわかることになります．
同じことなのですが，大小の向きを変えて次の問題を考えます．

長さ$N$の配列の各点に対して，自分より右にあって最初に自分より大きくなるものの位置を求めたい

これを，愚直に考えると各$i$に対して$i+1$から順に探していくというのを$N$回繰り返すと$\mathcal{O}(N^2)$になりますが，うまく視点を変えて走査することで$\mathcal{O}(N)$で計算することができます．

ポイント 定年のない世界で自分が何年のあいだ後輩より強いままでいられるかを考える

実は，よく考えると先ほどのスライド最小値の世界で卒業による引退がない状況と同じだという事が分かります．卒業がないので，番長順番待ちキューは一向に左側からは消化されないで，各人は自分より強い後輩が入ってこない限りキューに残り続け，自分より強い後輩が入ってきたその時に初めてキューから降りることができます．そう考えると，各人が最初にであう自分より強い後輩が，取りも直さずこの小問題の求めたいものになります．

なので，同様に番長順番待ちキューをシミュレートするように実装すればいいです．先に述べたように左からキューを抜けることがなく右側からしかキューを抜けないため，スタックを使って実装するので十分になります．

first_exceeder.py

def first_exceeder(a):
    # exceeder[i]: iより右側で a[i]を最初に超えるaのインデックス
    N = len(a)
    exceeder = [0] * N
    stk = [] #番長順番待ちキュー
    for i in range(0,N):
        # iが入学
        while len(stk) > 0:
            righttail = stk[-1]
            if a[righttail] < a[i]:
                exceeder[righttail] = i #順番待ちキューのセンパイが自分より弱い場合，センパイに自分の名前を告げて引導を渡す
                stk.pop()               #センパイがキューから離れる
                continue
            break
        stk.append(i)  # 自分がキューに並ぶ
    
    # 自分より強い後輩が入ってこなかったメンバーはキューに残ったままなので右端をexceederにする
    for i in stk:
        exceeder[i] = N
    return exceeder

先のスライド最大値の実装をそのまま改造してもいいですが，入学したときに先輩に引導を渡すというイメージで書き直しています．計算量は同じように$\mathcal{O}(N)$になります．

終わりに

なんだか競争社会の虚しさみたいな後味の解説になってしまいましたが，理解の一助になれば幸いです．