Problem :

https://leetcode.com/problems/largest-rectangle-in-histogram/


My Solution :

class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights.append(0)
stack = [-1]
area = 0
for i, height in enumerate(heights):
while height < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1
area = max(area, h*w)
stack.append(i)
return area


Comment :

원래 FM대로 하면 아래와 같이 코드가 길어야 하는데, 위 처럼 heights에 0을 추가하고 stack에 -1을 넣고 시작하면 코너 케이스 검증을 회피할 수 있다.


My Solution 2 :

class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
area = i = 0
while i < len(heights):
while stack and heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
if stack:
w = i - stack[-1] - 1
else:
w = i
area = max(area, h*w)
stack.append(i)
i += 1
while stack:
h = heights[stack.pop()]
if stack:
w = i - stack[-1] - 1
else:
w = i
area = max(area, h*w)
return area
secret