leetcode hard : largest rectangle in histogram

Largest Rectangle in Histogram - LeetCode

Largest Rectangle in Histogram - LeetCode

 

리트코드에서 유명한 문제 중 하나다.

처음 접하면 실로 어렵다 정말..!

난 오늘 두 번째 풀었는데도 아직 새롭다 ㅋㅋㅋㅋㅋ

진짜 대략적인 아이디어는 금방 떠올렸는데 디테일한 부분에서 아직 부족해서 내 예전 답을 보고 비교했다.

 

아이디어는 간단하다.

일단 특정 막대기 i에 대해서 그 막대기가 포함된 최대 넓이의 직사각형은 어떻게 구할까?

그 막대 높이 기준으로 가로로 선을 찍 그어보면 된다.

선을 그을수있는만큼 그으면 그 선의 길이가 최대 width가 되고 막대의 height를 곱하면 특정 막대 i를 포함하는 최대 넓이의 직사각형을 알 수 있다.

이걸 좀 수학적으로 표현하자면 특정 바 i의 높이가 h[i]일 때

i보다 왼쪽에 있는 바 a 중에 (a < i ) 높이가 h[i]보다 작은것중에 젤 오른쪽에 있는 바를 찾고

i보다 오른쪽에 있는 바 b중에 (i < b) 높이가 h[i]보다 작은것중에 젤 왼쪽에 있는 바를 찾으면

(b의 인덱스 - a의 인덱스 - 1)이 가로의 길이가 된다.

이 원리를 이용하면 스택을 이용해 문제를 풀 수 있다.

 

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = [ (-1,0) ]
        heights += [0]
        ans = heights[0]
        for i in range(len(heights)):
            h = heights[i]
            while len(stack)>1 and h < stack[-1][1]:
                ans = max(ans, (i-stack[-2][0]-1) * stack.pop()[1])
            stack.append( (i,h) )

                
        return ans

 

처음에 스택에 더미데이터를 넣는데 이게 없으면 첫 번째 바가 포함된 최대 넓이의 직사각형 넓이를 구할 수가 없다

heights의 마지막에도 더미데이터를 넣는데 이게 있어야 마지막 바가 포함된 최대 넓이의 직사각형 넓이를 수월하게 구할 수 있다.

 

코딩 인터뷰에서 이런 문제를 처음 맞닥뜨리게 된다면 그냥 아무말도 못하고 그날 술먹으러 갔을 것..ㅋㅋㅋ