[LeetCode][Python3] 84. Largest Rectangle in Histogram

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