C++で解く「最大幅ランプ」問題 ― 単調スタックによるO(n)アルゴリズム

問題概要

整数の配列 A が与えられます。「ランプ」とは、i < j かつ A[i] <= A[j] を満たすインデックスの組 (i, j) のことを指し、その幅は j − i で定義されます。求めたいのは、配列 A の中で幅が最大となるランプの幅です。条件を満たすランプがひとつも存在しない場合は 0 を返します。

たとえば入力が [6, 0, 8, 2, 1, 5] の場合、答えは 4 になります。(i, j) = (1, 5) を選べば A[1] = 0 ≤ A[5] = 5 が成立し、幅は 5 − 1 = 4 となるためです。

アプローチ：単調スタック

すべての組み合わせを総当たりで調べると計算量は O(n²) となり、大きな入力では非現実的です。そこで有効なのが「単調スタック（Monotonic Stack）」というテクニックです。全体の流れは次の2段階です。

1. 左端候補の収集（前方向の走査）： 左から順に見ていき、スタック内のどの値よりも小さい値を持つインデックスだけをスタックに積みます。こうするとスタック内の値は常に単調減少となり、ランプの左端になり得る要素だけが残ります。
2. 幅の最大化（後方向の走査）： 配列を右端から左へ向かって走査します。スタックの先頭は「最も左側にある最も小さい値」なので、A[スタックの先頭] ≤ A[i] が成り立つ限り、幅 i − 先頭インデックス を答えの候補として更新し、該当する要素をポップします。一度ポップされたインデックスは、それ以降（より左の i）では絶対に良い結果を生まないため、削除しても問題ありません。

解法の手順

• n := 配列のサイズ、ret := 0 とし、int 型のスタック st を用意します。
• i を 0 から n − 1 まで順番に処理します。
  • st が空、または A[st.top()] > A[i] を満たすとき、i を st にプッシュします。
• i を n − 1 から ret + 1 まで降順に処理します。
  • st が空でなく、かつ A[st.top()] <= A[i] である間、次を繰り返します。
    • ret := max(ret, i − st.top()) として最大幅を更新します。
    • st から要素をポップします。
• 最終的な ret の値を返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int maxWidthRamp(vector<int>& A) {
        int n = A.size();
        int ret = 0;
        stack<int> st;
        for(int i = 0; i < n; i++){
            if(st.empty() || A[st.top()] > A[i]){
                st.push(i);
            }
        }
        for(int i = n - 1; i > ret; i--){
            while(!st.empty() && A[st.top()] <= A[i]){
                ret = max(ret, i - st.top());
                st.pop();
            }
        }
        return ret;
    }
};
main(){
    vector<int> v1 = {6,0,8,2,1,5};
    Solution ob;
    cout << (ob.maxWidthRamp(v1));
}

入力

[6,0,8,2,1,5]

出力

4

動作の確認（トレース）

入力 [6, 0, 8, 2, 1, 5] を使って、アルゴリズムの実際の動きを確認してみましょう。

前方向の走査：

• i = 0：スタックが空なので 0 をプッシュ → スタック: [0]（値 6）
• i = 1：A[0] = 6 > 0 なので 1 をプッシュ → スタック: [0, 1]（値 6, 0）
• i = 2〜5：いずれも A[1] = 0 より大きいため、何もプッシュされません。

後方向の走査：

• i = 5：A[1] = 0 ≤ 5 なので、ret = max(0, 5 − 1) = 4 と更新し、1 をポップ。次の先頭 A[0] = 6 は 5 より大きいため、ここで終了します。
• ループ条件 i > ret を満たさなくなるため、これ以上の走査は不要です。

結果として 4 が返ります。

計算量

• 時間計算量： O(n) — 各インデックスは高々1回プッシュされ、高々1回ポップされるだけだからです。
• 空間計算量： O(n) — 最悪ケース（単調減少の配列など）では、スタックにすべてのインデックスが格納される可能性があります。