単調スタック（Monotonic Stack）パターン

中級

カテゴリ: データ構造

概要

単調スタックは、要素が常に単調増加または単調減少の順序で並ぶように維持されるスタックです。このデータ構造は、「次に大きい要素」や「次に小さい要素」を効率的に見つけるのに役立ちます。特に、配列内の各要素について、その右側（または左側）にある最初の大きい（または小さい）要素を見つける問題に効果的です。O(n)の時間複雑度で解決できるため、ブルートフォースアプローチ（O(n²)）よりも効率的です。

コードテンプレート

Java

Python

- 単調増加スタック（次に大きい要素を見つける）
public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1); // デフォルト値: 次に大きい要素がない場合は-1
    
    // スタックにはインデックスを格納
    Stack<Integer> stack = new Stack<>();
    
    for (int i = 0; i < n; i++) {
        // スタックが空でなく、現在の要素がスタックトップの要素より大きい場合
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            // スタックトップの要素の「次に大きい要素」は現在の要素
            int idx = stack.pop();
            result[idx] = nums[i];
        }
        // 現在のインデックスをスタックにプッシュ
        stack.push(i);
    }
    
    return result;
}

// Java - 単調減少スタック（次に小さい要素を見つける）
public int[] nextSmallerElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1); // デフォルト値: 次に小さい要素がない場合は-1
    
    Stack<Integer> stack = new Stack<>();
    
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
            int idx = stack.pop();
            result[idx] = nums[i];
        }
        stack.push(i);
    }
    
    return result;
}

Java

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

単調スタック次に大きい要素次に小さい要素ヒストグラムスタック操作単調増加単調減少左右の見通し効率的な検索O(n)の解法温度予測雨水トラップ要素間の関係インデックス追跡配列操作スタックの単調性

チャート式ひらめきポイント

問題を読んだときに、「ソート済み配列で何かを見つける」「二つの要素の関係を調べる」「効率的に配列を操作する」などの特徴があれば、双指針パターンが適用できる可能性が高いです。特に、O(n²)の計算量を避けたい場合に有効です。

このパターンを使用する問題例

1
次に大きい要素（Next Greater Element）: 配列内の各要素について、その右側にある最初の大きい要素を見つける
2
次に小さい要素（Next Smaller Element）: 配列内の各要素について、その右側にある最初の小さい要素を見つける
3
ヒストグラムの最大面積（Largest Rectangle in Histogram）: 棒グラフの最大の長方形面積を計算する
4
毎日の温度（Daily Temperatures）: 各日について、温度が上昇する次の日までの日数を計算する
5
雨水のトラップ（Trapping Rain Water）: 地形に溜まる雨水の量を計算する

このパターンを使う問題

このパターンを適用して解くことができる実際の問題です。

難

ヒストグラムの最大長方形

n個の非負整数の配列heightsが与えられます。この配列の各要素heightsは、幅1の棒グラフの高さを表します。ヒストグラム内で形成できる最大の長方形の面積を求めてください。...

中

最小スタック

スタックの基本操作（push、pop、top）をサポートし、さらに最小要素を定数時間で取得する操作（getMin）をサポートする「MinStack」クラスを設計してください。実装すべきメソッド： ...