503. 循環配列における次の大きな要素 II (Next Greater Element II)

循環配列（最後の要素の次が最初の要素となる配列）が与えられた場合、各要素に対して「次に大きい要素」を見つける問題です。要素xの次に大きい要素とは、配列を巡回順で走査した際、xの後に現れる最初のxより大きな数値を指します。そのような数値が存在しない場合は-1を出力します。

解法アプローチ：単調スタックの利用

通常の配列で「次に大きい要素」を見つける場合、単調スタック（Monotonic Stack）が有効です。本問題では配列が循環しているため、擬似的に配列の長さを2倍にして処理を行います。インデックス`i`を`0`から`2*n - 1`までループさせ、実際の配列へのアクセスは`i % n`で行うことで、循環走査をシミュレートできます。

スタックには配列のインデックスを格納し、スタック内の要素に対応する高さが単調増加になるように維持します。現在の要素がスタックのトップにある要素よりも大きい場合、スタックからポップ（取り出し）し、そのインデックスに対する結果を現在の要素で更新します。これを各列について処理することで、計算量O(n)で解を得ることができます。

実装コード（Python）

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [-1] * n
        stack = []  # インデックスを格納するスタック
        
        # 配列を2周分ループさせることで循環を表現
        for i in range(2 * n):
            current_index = i % n
            
            # スタックが空ではなく、現在の要素がスタックトップの要素より大きい場合
            while stack and nums[current_index] > nums[stack[-1]]:
                top_idx = stack.pop()
                result[top_idx] = nums[current_index]
            
            # 現在のインデックスをスタックに追加
            # ※n以上のインデックスは result 配列の範囲外なので result の更新は行われない
            stack.append(current_index)
            
        return result

42. 雨水を貯める (Trapping Rain Water)

高さと幅が1の柱が複数並んでいるとき、降雨後にこれらの柱の間に合計でどれだけの水が溜まるかを計算する問題です。

解法アプローチ1：動的計画法による最適化

各位置`i`に溜まる水の量は、その位置の左側にある柱の最大高さ(`leftMax`)と右側にある柱の最大高さ(`rightMax`)のうち、小さい方の値に依存します。具体的には、`min(leftMax[i], rightMax[i]) - height[i]`がその位置での水深となります。

このアプローチでは、まず左から右へ走査して各位置までの左側の最大高さを配列に記録し、次に右から左へ走査して右側の最大高さを記録します。最後にこれらを用いて各位置の水量を合計します。時間計算量はO(n)、空間計算量はO(n)です。

実装コード（Java）

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        int totalWater = 0;

        // 左側の最大高さを計算
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        // 右側の最大高さを計算
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        // 水の総量を計算
        for (int i = 0; i < n; i++) {
            int waterLevel = Math.min(leftMax[i], rightMax[i]);
            totalWater += waterLevel - height[i];
        }

        return totalWater;
    }
}

解法アプローチ2：単調スタック（行方向の計算）

この問題は単調スタックを用いても解くことができます。スタックにはインデックスを格納し、スタック内の要素に対応する高さが単調減少（スタックトップにいくほど低い）になるように維持します。

現在の柱の高さがスタックトップの柱の高さより高い場合、凹み（くぼ地）が形成されたとみなせます。スタックからポップして「底」となる位置を取得し、新しいスタックトップ（左側の壁）と現在の柱（右側の壁）を使って面積を計算します。

• 幅: `現在のインデックス - 左側の壁のインデックス - 1`
• 高さ: `min(左側の壁の高さ, 右側の壁の高さ) - 底の高さ`

同じ高さの柱が連続する場合、計算上は最も右にある柱を基準とするため、スタック内のインデックスを更新します。

実装コード（Python）

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []  # インデックスを格納、高さは単調減少を維持
        total_volume = 0
        n = len(height)
        
        for i in range(n):
            # 同じ高さの柱の場合は、右側のインデックスを使うために更新
            while stack and height[i] == height[stack[-1]]:
                stack.pop()
            
            # 現在の柱がスタックトップより高い場合、水を計算
            while stack and height[i] > height[stack[-1]]:
                bottom_idx = stack.pop() # 凹みの底
                
                if not stack:
                    break
                    
                left_idx = stack[-1] # 凹みの左側の壁
                
                # 幅の計算
                width = i - left_idx - 1
                # 高さの計算
                h = min(height[left_idx], height[i]) - height[bottom_idx]
                
                total_volume += h * width
            
            stack.append(i)
            
        return total_volume