LeetCode: 84. Largest Rectangle in Histogram

문제 링크: https://leetcode.com/problems/largest-rectangle-in-histogram/

O(N)만에 푸는 방법을 떠올리는 것은 매우 어렵다.

이 문제를 O(N)에 풀 수 있는 방법은 monotonic stack을 이용하는 것이다.

Monotonic Stack이란 stack을 쌓되 stack 내부가 오름차순 혹은 내림차순으로 정렬되도록 쌓는 것이다.

이 문제에서 Monotonic Stack이 사용되는 이유는 다음과 같다.

왼쪽에서부터 오른쪽으로 가면서 블록이 하나씩 추가된다고 고려했을 때,

이전에 추가된 블록에 비해 현재 블록의 높이가 작다면,

이전 블록의 높이가 직사각형의 최대 높이가 된다.

아래 그림에서 높이 2의 블록 차례가 오면,

높이 5와 높이 6의 블록은 더 이상 앞으로 영향을 주지 않는다.

 

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = [[-1, -1]]
        heights.append(0)
        ret = 0
        for i, h in enumerate(heights):
            if h >= stack[-1][1]:
                stack.append([i, h])
            else:
                while stack[-1][1] > h:
                    pi, ph = stack.pop()
                    ret = max(ret, (i-stack[-1][0]-1)*ph)
                stack.append([i, h])
        return ret