프로그래밍/LeetCode
[LeetCode][Python3] 84. Largest Rectangle in Histogram
snoopybox
2019. 4. 15. 01:13
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