dp-ヒストグラムの最大の面積について
概要
- 単調減少、単調増加でもない大きさが入り乱れたヒストグラムがある時、どのような四角形の切り取り方が最大の面積となるか
- queを用意して、queの末尾より小さい要素があった場合、そこから後ろにたどっていって面積を求めていく
具体例
from typing import List
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
return solve(heights)
from collections import deque
def solve(nums):
nums.append(0)
que = deque([-1])
ans = 0
for i in range(len(nums)):
# 減少に転じたら、大きさをすべて計算してmaxで保存
# queの並び順は単調増加になっているので、すべてのあり得るパターンを計算できる
while que and nums[que[-1]] > nums[i]:
idx = que.pop()
h = nums[idx]
w = i - que[-1] - 1
ans = max(h*w, ans)
que.append(i)
return ans
print(solve([2,1,5,6,2,3]))
print(solve([2,4]))