単調スタックの基本概念

単調スタック（Monotonic Stack）は、スタック内の要素が常に単調増加、または単調減少の順序を保つように維持するデータ構造です。この特性を利用することで、配列内の各要素に対して「左側または右側で最も近い、より大きい（または小さい）要素」を効率的に探索することができます。

典型的な応用としては、以下の 4 つのパターンがあります。

• 左側で最も近く、値が小さい要素のインデックス
• 右側で最も近く、値が小さい要素のインデックス
• 左側で最も近く、値が大きい要素のインデックス
• 右側で最も近く、値が大きい要素のインデックス

基本実装パターン

単調スタックの基本的な動作は、配列を走査しながらスタックにインデックスを蓄積します。新しい要素を処理する際、スタックの頂点にある要素との大小関係を確認し、単調性を崩す場合は頂点要素を弹出します。この弹出されるタイミングこそが、特定の条件を満たす境界を見つける瞬間となります。

例えば、単調増加スタックを維持する場合、現在の要素がスタック頂点の要素以下であれば、頂点要素を弹出します。このとき、弹出された要素にとっての「右側で最も近い小さい要素」が現在の要素であり、「左側で最も近い小さい要素」が弹出後の新しいスタック頂点となります。

def get_nearest_smaller_indices(data):
    size = len(data)
    result = [[] for _ in range(size)]
    stack = []
    
    # 最初のインデックスをプッシュ
    stack.append(0)
    
    for idx in range(1, size):
        # 単調性を維持するために条件を満たす限り弹出
        while stack and data[stack[-1]] >= data[idx]:
            current_idx = stack.pop()
            # 左側の境界：弹出後のスタック頂点、なければ -1
            left_bound = stack[-1] if stack else -1
            # 右側の境界：現在のインデックス
            right_bound = idx
            result[current_idx] = [left_bound, right_bound]
        
        stack.append(idx)
    
    # 残っている要素は右側に境界がないため -1
    while stack:
        current_idx = stack.pop()
        left_bound = stack[-1] if stack else -1
        result[current_idx] = [left_bound, -1]
        
    return result

応用問題：每日の気温

この問題では、ある日の気温よりも高くなるまでの waiting days を求めます。これは「右側で最も近く、値が大きい要素までの距離」を求める問題に変換できます。単調減少スタックを用いて実装します。

def calculate_waiting_days(temps):
    size = len(temps)
    days = [0] * size
    stack = []
    
    for idx in range(size):
        # 現在の気温がスタック頂点の気温より高ければ解決
        while stack and temps[idx] > temps[stack[-1]]:
            prev_idx = stack.pop()
            days[prev_idx] = idx - prev_idx
        stack.append(idx)
        
    return days

応用問題：部分配列の最小値の総和

すべての連続する部分配列における最小値の合計を計算します。各要素について、それが最小値となる部分配列の個数を求め、要素値を掛けることで貢献度を計算します。範囲は「左側の境界」から「右側の境界」までとなります。

def compute_subarray_min_sum(arr):
    MOD = 10**9 + 7
    size = len(arr)
    stack = []
    total_sum = 0
    
    # 右側の境界を見つけるために番兵として末尾に処理を追加する感覚で実施
    for idx in range(size + 1):
        current_val = arr[idx] if idx < size else 0
        
        while stack and arr[stack[-1]] >= current_val:
            mid_idx = stack.pop()
            left_idx = stack[-1] if stack else -1
            right_idx = idx
            
            count = (mid_idx - left_idx) * (right_idx - mid_idx)
            total_sum = (total_sum + count * arr[mid_idx]) % MOD
            
        stack.append(idx)
        
    return total_sum

応用問題：ヒストグラム内の最大矩形

各バーを高さとした矩形の最大面積を求めます。考え方は最小値の総和問題と類似しており、各バーが高さとして採用される最大の幅（左境界から右境界まで）を単調スタックで特定します。

def find_max_histogram_area(heights):
    stack = []
    max_area = 0
    size = len(heights)
    
    for idx in range(size + 1):
        current_h = heights[idx] if idx < size else 0
        
        while stack and heights[stack[-1]] >= current_h:
            h = heights[stack.pop()]
            w = idx if not stack else idx - stack[-1] - 1
            max_area = max(max_area, h * w)
            
        stack.append(idx)
        
    return max_area

応用問題：最大矩形

二次元のバイナリ行列において、1 で構成される最大の矩形面積を探します。これは各行を底辺としたヒストグラム問題に帰着できます。各行ごとに高さを更新し、前述のヒストグラムアルゴリズムを適用します。

def solve_maximal_rectangle(grid):
    if not grid or not grid[0]:
        return 0
        
    rows = len(grid)
    cols = len(grid[0])
    heights = [0] * cols
    max_area = 0
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                heights[c] += 1
            else:
                heights[c] = 0
        
        # ヒストグラム計算のロジックをインラインまたは関数呼び出しで実施
        stack = []
        for c in range(cols + 1):
            h = heights[c] if c < cols else 0
            while stack and heights[stack[-1]] >= h:
                height = heights[stack.pop()]
                width = c if not stack else c - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(c)
            
    return max_area

応用問題：最大幅の傾斜

配列内のインデックス i と j (i < j) において、nums[i] <= nums[j] を満たす j - i の最大値を求めます。まず単調減少スタックに候補となる i を保存し、その後配列を後方から走査して最大の幅を更新します。

def find_max_width_ramp(nums):
    size = len(nums)
    stack = []
    
    # 単調減少するインデックスをスタックに積む
    for idx in range(size):
        if not stack or nums[idx] < nums[stack[-1]]:
            stack.append(idx)
            
    max_width = 0
    # 後方から走査して条件を満たす最大距離を探す
    for idx in range(size - 1, -1, -1):
        while stack and nums[idx] >= nums[stack[-1]]:
            start_idx = stack.pop()
            max_width = max(max_width, idx - start_idx)
            
    return max_width

応用問題：重複しない最小の文字列

文字列から重複する文字を削除し、辞書順で最小となる文字列を生成します。各文字の残りの出現回数をカウントし、単調増加スタックを維持しながら、後続に同じ文字があれば弹出できるか判断します。

def get_smallest_subsequence(s):
    from collections import Counter
    
    count = Counter(s)
    stack = []
    in_stack = set()
    
    for char in s:
        count[char] -= 1
        
        if char in in_stack:
            continue
            
        # 辞書順を小さくするため、条件を満たせば頂点を弹出
        while stack and char < stack[-1] and count[stack[-1]] > 0:
            removed = stack.pop()
            in_stack.remove(removed)
            
        stack.append(char)
        in_stack.add(char)
        
    return "".join(stack)