問題
n個の非負整数の配列heightsが与えられます。この配列の各要素heightsは、幅1の棒グラフの高さを表します。 ヒストグラム内で形成できる最大の長方形の面積を求めてください。
例
制約
- 1 <= heights.length <= 10^5
- 0 <= heights[i] <= 10^4
解法
アプローチ
この問題は、単調スタック（monotonic stack）を使用して効率的に解くことができます。 基本的なアイデアは、各棒について、その棒を高さとする最大の長方形を見つけることです。そのためには、各棒の左右に、その棒よりも低い棒が現れる位置を見つける必要があります。 単調増加スタックを使用すると、各棒について、左側と右側の「次に小さい要素」を効率的に見つけることができます。 【アルゴリズムの流れ】 1. 単調増加スタックを用意します（スタックには棒のインデックスを格納） 2. 配列を左から右へ走査します 3. 現在の棒の高さが、スタックの先頭の棒の高さよりも小さい場合： - スタックから棒をポップします - ポップした棒を高さとする長方形の面積を計算します - 幅は、現在の位置から、新しいスタックの先頭の位置までです - 最大面積を更新します 4. 現在の棒のインデックスをスタックにプッシュします 5. 配列の走査が終わった後、スタックに残っている棒についても同様に処理します 【視覚的な例】 heights = [2,1,5,6,2,3] の場合： 1. i=0, heights[0]=2: スタックは空なので、インデックス0をプッシュ。スタック=[0] 2. i=1, heights[1]=1: heights[1] < heights[0]なので、インデックス0をポップ。 - 高さ2、幅1の長方形の面積は2。最大面積=2 - スタックは空になったので、インデックス1をプッシュ。スタック=[1] 3. i=2, heights[2]=5: heights[2] > heights[1]なので、インデックス2をプッシュ。スタック=[1,2] 4. i=3, heights[3]=6: heights[3] > heights[2]なので、インデックス3をプッシュ。スタック=[1,2,3] 5. i=4, heights[4]=2: heights[4] < heights[3]なので、インデックス3をポップ。 - 高さ6、幅1の長方形の面積は6。最大面積=6 - heights[4] < heights[2]なので、インデックス2をポップ。 - 高さ5、幅2の長方形の面積は10。最大面積=10 - heights[4] > heights[1]なので、インデックス4をプッシュ。スタック=[1,4] 6. i=5, heights[5]=3: heights[5] > heights[4]なので、インデックス5をプッシュ。スタック=[1,4,5] 7. 配列の走査が終わった後、スタックに残っているインデックスを処理： - インデックス5をポップ: 高さ3、幅1の長方形の面積は3 - インデックス4をポップ: 高さ2、幅2の長方形の面積は4 - インデックス1をポップ: 高さ1、幅6の長方形の面積は6 最大面積は10です。
計算量
時間計算量
O(n) - 各要素は最大で1回だけスタックにプッシュされ、1回だけポップされるため
空間計算量
O(n) - スタックのサイズ
実装
Javaの実装
/**
* ヒストグラムの最大長方形問題の解法
*
* 【問題】
* n個の非負整数の配列heightsが与えられます。この配列の各要素heightsは、幅1の棒グラフの高さを表します。
* ヒストグラム内で形成できる最大の長方形の面積を求めてください。
*
* 【アプローチ】
* 単調スタックを使用して、各棒について、左右に自分より低い棒が現れる位置を効率的に見つけます。
* これにより、各棒を高さとする最大の長方形の面積を計算できます。
*
* 【計算量】
* - 時間計算量: O(n) - 各要素は最大で1回だけスタックにプッシュされ、1回だけポップされる
* - 空間計算量: O(n) - スタックのサイズ
*/
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int maxArea = 0;
Stack<Integer> stack = new Stack<>(); // インデックスを格納するスタック
for (int i = 0; i <= n; i++) {
// 現在の高さ（配列の範囲外の場合は0）
int currentHeight = (i == n) ? 0 : heights[i];
// スタックが空でなく、現在の高さがスタックの先頭の棒の高さよりも小さい場合
while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {
// スタックから棒のインデックスをポップ
int height = heights[stack.pop()];
// 幅を計算（現在の位置から、新しいスタックの先頭の位置まで）
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
// 面積を計算し、最大面積を更新
maxArea = Math.max(maxArea, height * width);
}
// 現在のインデックスをスタックにプッシュ
stack.push(i);
}
return maxArea;
}
}解説
この解法では、単調増加スタックを使用して、各棒について、左右に自分より低い棒が現れる位置を効率的に見つけています。
【詳細な解説】
1. **アルゴリズムの概要**: - 単調増加スタックを使用して、各棒について、左右に自分より低い棒が現れる位置を見つけます。 - これにより、各棒を高さとする最大の長方形の面積を計算できます。
2. **実装の詳細**: - スタックにはインデックスを格納します。 - 配列を左から右へ走査し、各位置で以下の処理を行います： - 現在の棒の高さが、スタックの先頭の棒の高さよりも小さい場合、スタックから棒をポップし、その棒を高さとする長方形の面積を計算します。 - 幅は、現在の位置から、新しいスタックの先頭の位置までです。 - 最大面積を更新します。 - この処理を、スタックが空になるか、スタックの先頭の棒の高さが現在の棒の高さ以下になるまで繰り返します。 - 現在のインデックスをスタックにプッシュします。 - 配列の走査が終わった後、スタックに残っている棒についても同様に処理します（これを簡単にするために、配列の最後に高さ0の棒を追加したと考えます）。
3. **具体例**: heights = [2,1,5,6,2,3] の場合：
``` i=0, heights[0]=2: スタック=[0] i=1, heights[1]=1: heights[1] < heights[0]なので、インデックス0をポップ。 - 高さ2、幅1の長方形の面積は2。最大面積=2 - スタックは空になったので、インデックス1をプッシュ。スタック=[1] i=2, heights[2]=5: heights[2] > heights[1]なので、インデックス2をプッシュ。スタック=[1,2] i=3, heights[3]=6: heights[3] > heights[2]なので、インデックス3をプッシュ。スタック=[1,2,3] i=4, heights[4]=2: heights[4] < heights[3]なので、インデックス3をポップ。 - 高さ6、幅1の長方形の面積は6。最大面積=6 - heights[4] < heights[2]なので、インデックス2をポップ。 - 高さ5、幅2の長方形の面積は10。最大面積=10 - heights[4] > heights[1]なので、インデックス4をプッシュ。スタック=[1,4] i=5, heights[5]=3: heights[5] > heights[4]なので、インデックス5をプッシュ。スタック=[1,4,5] i=6（配列の範囲外）: currentHeight=0として処理。 - heights[5]=3 > 0なので、インデックス5をポップ。 - 高さ3、幅1の長方形の面積は3。 - heights[4]=2 > 0なので、インデックス4をポップ。 - 高さ2、幅2の長方形の面積は4。 - heights[1]=1 > 0なので、インデックス1をポップ。 - 高さ1、幅6の長方形の面積は6。 ```
最大面積は10です。
4. **最適化**: - この実装では、配列の最後に高さ0の棒を追加したと考えることで、スタックに残っている棒の処理を簡単にしています。 - 実際には、配列の範囲外のインデックスを処理する際に、高さを0として扱っています。
追加のメモ
この問題は、単調スタック（monotonic stack）の典型的な応用例です。単調スタックは、「次に大きい要素」や「次に小さい要素」を効率的に見つけるのに役立ちます。 【単調スタックとは】 単調スタックとは、スタック内の要素が常に単調（増加または減少）に並んでいるスタックです。この問題では、単調増加スタックを使用しています。 【異なる解法の比較】 1. **ブルートフォースアプローチ** - 各棒について、左右に拡張できる範囲を見つけて面積を計算 - 時間計算量: O(n²) - 空間計算量: O(1) - 問題点: 大きな入力に対して非効率 2. **分割統治法** - 配列を分割し、左半分、右半分、および両方にまたがる長方形の最大面積を計算 - 時間計算量: O(n log n) - 空間計算量: O(log n)（再帰スタック） - 問題点: 実装が複雑 3. **単調スタックを使用するアプローチ（上記の解法）** - 各棒について、左右に自分より低い棒が現れる位置を効率的に見つける - 時間計算量: O(n) - 空間計算量: O(n) - 利点: 効率的で実装も比較的シンプル 【実装のバリエーション】 1. **2回の走査** - 1回目の走査で、各棒の左側に自分より低い棒が現れる位置を見つける - 2回目の走査で、各棒の右側に自分より低い棒が現れる位置を見つける - 各棒について、これらの情報を使って面積を計算 - 時間計算量: O(n) - 空間計算量: O(n) - 利点: 理解しやすい 2. **1回の走査（上記の解法）** - 単調スタックを使用して、1回の走査で各棒の左右に自分より低い棒が現れる位置を見つける - 時間計算量: O(n) - 空間計算量: O(n) - 利点: より効率的 【関連する問題】 - 「ヒストグラムの最大長方形」（Largest Rectangle in Histogram） - 「最大の長方形」（Maximal Rectangle）: 二次元バイナリマトリックス内の最大の長方形を見つける問題 - 「次に大きい要素」（Next Greater Element）: 配列内の各要素について、その右側にある最初の大きい要素を見つける問題 - 「次に小さい要素」（Next Smaller Element）: 配列内の各要素について、その右側にある最初の小さい要素を見つける問題 この問題は、単調スタックの基本的な使い方を理解するための良い例です。単調スタックは、「次に大きい/小さい要素」を見つける問題や、この問題のようにヒストグラムの処理に関連する問題で頻繁に使用されます。