ヒストグラム内の最大長方形
単調スタックで左端の境界を追跡し、1回の走査でヒストグラム内に収まる長方形の最大面積を計算します。
「ヒストグラム内の最大長方形」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
問題：ヒストグラム内の最大長方形
ヒストグラム内の最大長方形問題（LeetCode 84）では、各棒の高さを表す0以上の整数配列が与えられます。各棒の幅は1です。ヒストグラム内に作成できる最大の長方形の面積を求めます。長方形は連続した棒にまたがる必要があり、その高さは含まれる棒のうち最も短い棒によって制限されます。
単純な方法では、すべての組 (i, j) について [i, j] 内の最小の高さを求め、(j - i + 1) と掛け合わせます。これは O(n³) となり、最小値を事前計算しても O(n²) なので、遅すぎます。単調スタックによる解法は O(n) で実行できます。
# Example: heights = [2, 1, 5, 6, 2, 3]
# Rectangles:
# width=1, height=6 at index 3 => area=6
# width=2, height=5 at indices 2-3 => area=10 (maximum!)
# width=6, height=1 across all => area=6
# width=3, height=2 at indices 2-4 => area=6
heights = [2, 1, 5, 6, 2, 3]
print('Heights:', heights)
print('Expected max area: 10 (bars of height 5 and 6, width 2)')
# Brute force for small inputs:
def brute_force(heights):
n = len(heights)
max_area = 0
for i in range(n):
min_h = heights[i]
for j in range(i, n):
min_h = min(min_h, heights[j])
max_area = max(max_area, min_h * (j - i + 1))
return max_area
print('Brute force answer:', brute_force(heights)) # 10各棒の長方形を制限するもの
高さ h の棒 i が最小値となる最大の長方形は、左方向には h より低い最初の棒まで、右方向にも h より低い最初の棒まで広がります。幅は right_boundary - left_boundary - 1 で、面積は h × width です。
この見方をすると、問題は各棒について前のより小さい要素（PSE）と次のより小さい要素（NSE）を求める問題になります。これらは、単調増加スタックによってそのまま計算できます。短い棒が見つかって棒 i を pop した瞬間、現在の棒がその NSE となり、pop 後のスタックトップがその PSE となります。
heights = [2, 1, 5, 6, 2, 3]
n = len(heights)
# Find PSE and NSE for each bar
pse = [-1] * n # index of previous smaller element
nse = [n] * n # index of next smaller element (default: beyond array)
# PSE
stack = []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
# NSE
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
max_area = 0
for i in range(n):
width = nse[i] - pse[i] - 1
area = heights[i] * width
print(f'Bar {i} (h={heights[i]}): PSE={pse[i]}, NSE={nse[i]}, width={width}, area={area}')
max_area = max(max_area, area)
print('Max area:', max_area)単調スタックによる1回の走査での解法
上記の2回走査する方法でも動作しますが、1回の走査にまとめることができます。単調増加スタックを使って棒を左から右へ処理します。棒 i がスタックのトップより短い場合、トップの棒を pop します。pop された棒の高さが長方形の高さ、右端が i、左端が新しいスタックトップ + 1 になります。
標準的な方法として、heights の末尾にセンチネル 0 を追加します。これにより、自然には短い棒が現れない場合でも、最後にすべての棒がスタックから pop されます。センチネルがない場合は、ループ終了後にスタックに残った要素を処理する必要があります。
def largest_rectangle(heights):
stack = [] # monotonic increasing: indices of bars
max_area = 0
heights = heights + [0] # sentinel: forces all bars to be popped
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()] # height of the rectangle
width = i if not stack else i - stack[-1] - 1 # left boundary
max_area = max(max_area, height * width)
stack.append(i)
return max_area
print(largest_rectangle([2, 1, 5, 6, 2, 3])) # 10
print(largest_rectangle([2, 4])) # 4
print(largest_rectangle([1, 1])) # 2
print(largest_rectangle([0, 9])) # 9
print(largest_rectangle([6, 7, 5, 2, 4, 5, 9, 3])) # 161回の走査で行うアルゴリズムの追跡
センチネルを含む [2, 1, 5, 6, 2, 3, 0] を1ステップずつ追ってみます。
- i=0、h=2：0 を push します。スタック: [0]
- i=1、h=1：0 を pop します（h=2、width=1、area=2）。スタックが空になったので、1 を push します。スタック: [1]
- i=2、h=5：5>1 なので、2 を push します。スタック: [1,2]
- i=3、h=6：6>5 なので、3 を push します。スタック: [1,2,3]
- i=4、h=2：3 を pop します（h=6、width=4-2-1=1、area=6）。2 を pop します（h=5、width=4-1-1=2、area=10★）。2>1 なので停止します。4 を push します。スタック: [1,4]
- i=5、h=3：3>2 なので、5 を push します。スタック: [1,4,5]
- i=6、センチネル h=0：すべてを pop し、面積を計算します。
def largest_rectangle_trace(heights):
stack = []
max_area = 0
hs = heights + [0]
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = hs[top] * w
print(f' Pop bar {top} (h={hs[top]}): width={w}, area={area}', end='')
if area > max_area:
max_area = area
print(' *** NEW MAX ***', end='')
print()
print(f'i={i} h={h}: push {i}, stack={[hs[s] for s in stack + [i]]}')
stack.append(i)
print(f'Max area: {max_area}')
return max_area
largest_rectangle_trace([2, 1, 5, 6, 2, 3])幅の計算：なぜ i - stack[-1] - 1 なのか
スタックから棒 j を pop すると、次のことが分かります。j の長方形の右端は i です。これは、右側で j より短い最初の棒が i だからです。左端は、pop 後のスタックで j のすぐ下にある棒です。これを k とします。したがって幅は i - k - 1 です（k+1 から i-1 までの棒が対象です）。
pop 後にスタックが空の場合、j の長方形は左端まで完全に広がります。幅は単純に i です（インデックス 0 から i-1 までで、すべて heights[j] 以上の高さです）。これは width = i if not stack else i - stack[-1] - 1 という特殊なケースです。
# Illustrating left/right boundary logic
heights = [1, 3, 5, 2]
# After processing with stack:
# When we pop bar 2 (h=5) at i=3 (h=2):
# stack after pop = [0, 1] => left boundary = 1+1=2, right=3-1=2 => width=1
# When we pop bar 1 (h=3) at i=3 (h=2):
# stack after pop = [0] => left boundary = 0+1=1, right=3-1=2 => width=2
# etc.
def compute_boundaries(heights):
hs = heights + [0]
stack = []
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
if stack:
left = stack[-1] + 1
width = i - stack[-1] - 1
else:
left = 0
width = i
print(f'Bar {top} (h={hs[top]}): extends from {left} to {i-1}, width={width}')
stack.append(i)
compute_boundaries([2, 1, 5, 6, 2, 3])バイナリ行列内の最大長方形
最大長方形（LeetCode 85）は、ヒストグラムの問題を2次元のバイナリ行列へ拡張したものです。各行について、各セルの上方向に連続する 1 の個数を高さとして計算します。これにより、その行に対応するヒストグラムが作られます。各行のヒストグラムに対して、ヒストグラム内の最大長方形を求めるアルゴリズムを適用します。すべての行で得られた最大値が答えです。
これにより、2次元の問題を、1次元のヒストグラム問題を n 回繰り返す形に変換できます。m 行 n 列の行列に対する時間計算量は O(m × n) です。各行についてヒストグラムを1回走査し、その走査が O(n) となります。
def maximal_rectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
max_area = 0
def hist_max_area(h):
stack, area = [], 0
for i, hh in enumerate(h + [0]):
while stack and h[stack[-1]] > hh:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = max(area, h[top] * w)
stack.append(i)
return area
for row in matrix:
for j in range(n):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
max_area = max(max_area, hist_max_area(heights[:]))
return max_area
matrix = [['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1'],
['1','0','0','1','0']]
print(maximal_rectangle(matrix)) # 6ヒストグラム問題のエッジケース
処理すべき重要なエッジケースは次のとおりです。
- すべて同じ高さ：配列全体が1つの長方形になります。答え = n × height
- 単調増加：センチネルまで pop は発生しません。最後の棒の面積が最大になります
- 棒が1本：答え = height[0]
- 高さ 0 の棒：自然なセンチネルとして機能し、ヒストグラムを独立した区間に分割します
末尾にセンチネル（0）を追加すると、単調増加の場合でも残ったすべての棒が最後に pop されます。センチネルがない場合は、メインの反復処理の後に別のクリーンアップループが必要です。
def largest_rectangle(heights):
stack = []
max_area = 0
heights = heights + [0]
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, heights[top] * w)
stack.append(i)
return max_area
# Edge cases
print(largest_rectangle([5, 5, 5, 5])) # 20 (all same)
print(largest_rectangle([1, 2, 3, 4, 5])) # 9 (increasing: 3*3)
print(largest_rectangle([5, 4, 3, 2, 1])) # 9 (decreasing: 3*3)
print(largest_rectangle([5])) # 5 (single bar)
print(largest_rectangle([0, 0, 0])) # 0 (all zero)
print(largest_rectangle([3, 0, 3])) # 3 (zero splits)分割統治による別解
ヒストグラムの問題は、分割統治でも解くことができます。最小の高さの棒を境に分割し、それぞれの半分を再帰的に解き、最小の高さを使って全幅に広がる長方形と比較します。平均計算量は O(n log n) ですが、ソート済みの入力では最悪の場合 O(n²) になります。
単調スタックによる方法は、最悪の場合でも O(n) なので、厳密に優れています。ただし、分割統治による方法を理解すると問題への直感が深まり、どの区間でも全幅の長方形の高さを制限するのは常に最小の高さの棒である理由も分かります。
def largest_rectangle_dc(heights, lo=0, hi=None):
if hi is None:
hi = len(heights) - 1
if lo > hi:
return 0
# Find the index of the minimum height in [lo, hi]
min_idx = lo
for i in range(lo, hi + 1):
if heights[i] < heights[min_idx]:
min_idx = i
# Three options:
# 1. Max rect entirely in left half
# 2. Max rect entirely in right half
# 3. Max rect spanning entire [lo, hi] with height = min
full_width_area = heights[min_idx] * (hi - lo + 1)
left_area = largest_rectangle_dc(heights, lo, min_idx - 1)
right_area = largest_rectangle_dc(heights, min_idx + 1, hi)
return max(full_width_area, left_area, right_area)
print(largest_rectangle_dc([2, 1, 5, 6, 2, 3])) # 10ヒストグラムのパターン：部分配列の個数
同じスタック手法を使う関連問題として、ヒストグラム内で最小要素が特定の目標値になる部分配列の個数を数える問題があります。各棒の PSE と NSE を計算し、(i - pse[i]) × (nse[i] - i) という式を使って解きます。この式は、棒 i が最小値となる部分ヒストグラムの個数を数えます。
この「左側の個数 × 右側の個数」という手法は、いくつかの LeetCode 問題に登場します。たとえば、部分配列の最小値の合計（907）、すべての文字が重複しない部分文字列の個数、要素の寄与を求める問題などです。単調スタックによって PSE と NSE を O(n) で計算できるため、各要素の寄与を O(1) で求められます。
def sum_of_subarray_minimums(arr):
n = len(arr)
pse = [-1] * n # previous strictly smaller element
nse = [n] * n # next smaller or equal element
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
MOD = 10**9 + 7
total = 0
for i in range(n):
left_count = i - pse[i] # subarrays where i is leftmost min
right_count = nse[i] - i # subarrays where i is the min
total += arr[i] * left_count * right_count
return total % MOD
print(sum_of_subarray_minimums([3, 1, 2, 4])) # 17
print(sum_of_subarray_minimums([11, 81, 94, 43, 3])) # 444実践的な面接のヒント
面接でヒストグラムの問題が出たら、次のチェックリストに従ってください：
- 確認する：高さは0でもよいか。出力は面積、インデックス、個数のどれか。
- まず全探索から始め、計算量が O(n²) または O(n³) であることを述べる
- 各棒の寄与は、左右それぞれで最も近い低い棒までの広がりに依存することを説明する
- PSE/NSE → 単調スタック → O(n) 解法を導入する
- 番兵のテクニック（0を追加）を使ってコードを簡潔にする
- ホワイトボードで小さな例をトレースする
よくある追加質問は、2D（最大長方形）への拡張です。これを n 個のヒストグラムの問題に分解でき、それぞれが O(n) なので、全体で O(m×n) になることを示してください。
# Final clean solution for interview
def largest_rectangle_in_histogram(heights):
stack = []
max_area = 0
for i, h in enumerate(heights + [0]): # sentinel forces final pops
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
# Verify all test cases from earlier
test_cases = [
([2, 1, 5, 6, 2, 3], 10),
([6, 7, 5, 2, 4, 5, 9, 3], 16),
([1], 1),
([2, 0, 2], 2),
([], 0),
]
for heights, expected in test_cases:
if not heights:
result = 0
else:
result = largest_rectangle_in_histogram(heights)
status = 'PASS' if result == expected else 'FAIL'
print(f'{status}: {heights} => {result} (expected {expected})')部分配列範囲の合計と類似のバリエーション
PSE/NSE のテクニックは、複数の LeetCode 問題に一般化できます。部分配列範囲の合計（2104）では、すべての部分配列について (最大値 - 最小値) の合計を求めます。これは、（部分配列の最大値の合計）から（部分配列の最小値の合計）を引いたものに等しく、それぞれを単調スタックで O(n) で計算できます。キュー内で見える人の数（1944）では、減少スタックを使い、ポップするたびに見える人を1人として数えます。この一群の問題を見分けるには、「各要素について、どこまで支配できるか」という問いに気づくことが重要です。その答えは常に、単調スタックを使った PSE/NSE です。
def sum_subarray_ranges(nums):
n = len(nums)
# Sum of subarray max - sum of subarray min
def contrib(arr, is_max):
# Count contribution of each element as max (or min)
n = len(arr)
left = [0]*n; right = [0]*n
stack = []
for i in range(n):
while stack and (arr[stack[-1]] < arr[i] if is_max else arr[stack[-1]] > arr[i]):
stack.pop()
left[i] = i - (stack[-1] if stack else -1)
stack.append(i)
stack = []
for i in range(n-1, -1, -1):
while stack and (arr[stack[-1]] <= arr[i] if is_max else arr[stack[-1]] >= arr[i]):
stack.pop()
right[i] = (stack[-1] if stack else n) - i
stack.append(i)
return sum(arr[i] * left[i] * right[i] for i in range(n))
return contrib(nums, True) - contrib(nums, False)
print(sum_subarray_ranges([1, 2, 3])) # 4
print(sum_subarray_ranges([1, 3, 3])) # 4
print(sum_subarray_ranges([4, -2, -3, 4, 1])) # 59クイックチェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認してください。
レッスンのまとめ
このレッスンでは、各棒について、その棒を含む最大の長方形の境界は、左右それぞれで最も近い低い棒によって決まる（PSE と NSE）こと、単調増加スタックは、棒がポップされる際に PSE/NSE の両方を見つけることで、1回の O(n) パスですべての境界を計算できること、そして番兵の 0 を追加するとスタック内のすべての棒が確実にポップされ、ループを1つにまとめてコードを簡潔にできることを学びました。次は、単調デックを使って O(n) でスライディングウィンドウの最大値を求めます。
よくある質問
「ヒストグラム内の最大長方形」レッスンは無料ですか？
はい。「ヒストグラム内の最大長方形」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「ヒストグラム内の最大長方形」で何を学びますか？
単調スタックで左端の境界を追跡し、1回の走査でヒストグラム内に収まる長方形の最大面積を計算します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「ヒストグラム内の最大長方形」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。