問題 42：雨水貯蔵量のカウント

本問題は、与えられた非負整数配列において、各柱の間に貯まる雨水の総量を求めるものです。解決策には主に動的計画法と単調スタックを利用した方法があります。

動的計画法の活用

それぞれの柱の位置において、蓄積可能な水の高さは「その位置の左側にある最も高い柱」および「右側にある最も高い柱」の较小値によって決定されます。これら二つの値を事前に計算して保存することで、O(N) の時間内で総量を算出できます。

実装のポイントとして、左側最大高さを記録する配列と、右側最大高さを記録する配列を用意します。まず左から右へ順に遍历して左側のピークを更新し、次に右から左へ遍历して右側のピークを埋めます。最後にそれぞれの位置における水深を合計します。

class Solution {
    public int trapRainWater(int[] elevationData) {
        int count = elevationData.length;
        if (count <= 2) {
            return 0;
        }

        // 左側および右側の最大高さを格納する配列
        int[] leftPeak = new int[count];
        int[] rightPeak = new int[count];

        // 左側最大の累積計算
        leftPeak[0] = elevationData[0];
        for (int idx = 1; idx < count; idx++) {
            leftPeak[idx] = Math.max(elevationData[idx], leftPeak[idx - 1]);
        }

        // 右側最大の累積計算
        rightPeak[count - 1] = elevationData[count - 1];
        for (int idx = count - 2; idx >= 0; idx--) {
            rightPeak[idx] = Math.max(elevationData[idx], rightPeak[idx + 1]);
        }

        // 全インデックスでの貯水量を合計
        int totalVolume = 0;
        for (int idx = 0; idx < count; idx++) {
            int waterLevel = Math.min(leftPeak[idx], rightPeak[idx]) - elevationData[idx];
            if (waterLevel > 0) {
                totalVolume += waterLevel;
            }
        }
        return totalVolume;
    }
}

単調スタックによる最適化

スタックを利用して、凹む部分（水が溜まりやすい場所）を効率的に見つけるアプローチです。ここでは、スタック内の要素が高さの順に並ぶことを保証し、より高い柱が見つかった際に水面計算を行います。

スタックからは栈頭部から下へ向かって高さが大きくなるように管理します。現在処理中の柱が栈顶柱よりも高い場合、中間の柱が底部となり、現在の柱が右壁、栈顶前の柱が左壁となります。これにより、横幅と高さを算出可能です。

同様の高さに遭遇した場合、最も右側のインデックスを保持するために既存のインデックスを上書きします。

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int calculateWaterAccumulation(int[] elevations) {
        int dataSize = elevations.length;
        if (dataSize < 3) return 0;

        Deque<Integer> storage = new ArrayDeque<>();
        storage.push(0);
        
        int accumulated = 0;

        for (int i = 1; i < dataSize; i++) {
            int currentVal = elevations[i];
            
            // 栈顶柱高度小于当前柱，出现凹陷，计算积水
            while (!storage.isEmpty() && elevations[storage.peek()] < currentVal) {
                int bottomIdx = storage.pop();
                
                if (storage.isEmpty()) break;
                
                int leftWall = storage.peek();
                int width = i - leftWall - 1;
                
                int minHeight = Math.min(elevations[leftWall], currentVal);
                int depth = minHeight - elevations[bottomIdx];
                
                accumulated += depth * width;
            }
            
            // 栈顶柱高度等于或大于当前柱时入栈
            if (storage.isEmpty() || elevations[i] < elevations[storage.peek()]) {
                storage.push(i);
            } else if (elevations[i] == elevations[storage.peek()]) {
                storage.pop();
                storage.push(i);
            }
        }
        return accumulated;
    }
}

問題 84：柱状図における最大長方形の面積

与えられた柱の高さのリストから、長方形の面積を最大化する部分を探索する問題です。

動的計画法（境界検索）

各柱を中心とした矩形の最大面積を求めるためには、「左右両端でその柱の高さ未満となる最初のインデックス」を知る必要があります。これらの境界点を事前に計算しておけば、各柱に対して矩形を確定させられます。

このアプローチでは、配列内を遡って探しますが、直接一つずつ辿るのではなく、すでに計算済みの境界点情報を参照することで効率化を図ります。これにより O(N) で動作するようになります。

class Solution {
    public int findMaxRectArea(int[] hValues) {
        int len = hValues.length;
        if (len == 0) return 0;

        int[] lowerLeftBoundary = new int[len];
        int[] lowerRightBoundary = new int[len];

        // 左側境界の初期化
        lowerLeftBoundary[0] = -1;
        for (int k = 1; k < len; k++) {
            int temp = k - 1;
            // 直前の低い値があるまでジャンプ
            while (temp >= 0 && hValues[temp] >= hValues[k]) {
                temp = lowerLeftBoundary[temp];
            }
            lowerLeftBoundary[k] = temp;
        }

        // 右側境界の初期化
        lowerRightBoundary[len - 1] = len;
        for (int k = len - 2; k >= 0; k--) {
            int temp = k + 1;
            // 右側の低い値があるまでジャンプ
            while (temp < len && hValues[temp] >= hValues[k]) {
                temp = lowerRightBoundary[temp];
            }
            lowerRightBoundary[k] = temp;
        }

        // 最大面積の算出
        int maxArea = 0;
        for (int i = 0; i < len; i++) {
            int currentArea = hValues[i] * (lowerRightBoundary[i] - lowerLeftBoundary[i] - 1);
            maxArea = Math.max(maxArea, currentArea);
        }
        return maxArea;
    }
}

単調スタックによる拡張解法

雨水貯蔵の問題とは逆に、ここでは「左右に隣接して低くなる柱」を探すために、降順の単調スタックを用います。栈頂から栈底に向かって高さが小さくなる順序を保ちます。

境界条件を扱う簡易化のため、元の配列の前後に高さ 0 のダミー要素を追加することで、ループ処理における特別なケース分けを省略します。処理中は、現在の柱が栈顶よりも低くなった時に、栈顶の要素を範囲終了とみなして面積を計算します。

import java.util.Stack;

class Solution {
    public int getLargestRectangle(int[] histogram) {
        // センチネルとして両端に 0 を追加
        int[] extendedBar = new int[histogram.length + 2];
        System.arraycopy(histogram, 0, extendedBar, 1, histogram.length);
        
        Stack<Integer> st = new Stack<>();
        st.push(0); // 先頭のダミー位置
        
        int maxVal = 0;
        
        for (int pos = 1; pos < extendedBar.length; pos++) {
            if (extendedBar[pos] >= extendedBar[st.peek()]) {
                st.push(pos);
            } else {
                while (!st.isEmpty() && extendedBar[pos] < extendedBar[st.peek()]) {
                    int mid = st.pop();
                    int left = st.peek();
                    int width = pos - left - 1;
                    int height = extendedBar[mid];
                    
                    if (width * height > maxVal) {
                        maxVal = width * height;
                    }
                }
                st.push(pos);
            }
        }
        return maxVal;
    }
}