84. Largest Rectangle in Histogram

[zeikar]

Problem link

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

Problem Summary

히스토그램이 있고 여기서 가장 큰 직사각형의 넓이를 구하는 문제.

Solution

이건 유명한 문제라 어떻게 보면 상식? 느낌.

스택을 쓰면 O(n)으로 풀 수 있다.

일단 키 포인트는 한 지점 까지의 최대 넓이를 구할 때 그보다 왼쪽에 큰 값이 있다면 그 큰 값은 무시된다는 것이다. 왜냐하면 현재 지점의 높이가 더 낮기 때문에 직사각형을 그렸을 때 포함되지 않기 때문이다. 비슷하게 오른쪽도 마찬가지이다.
그림을 그려가면서 하면 쉽게 이해할 수 있다.

문제 1번 예제로 보면 5, 6 다음 2가 나오는데 2부터 직사각형을 그린다고 하면 이전의 5, 6 에서 2보다 큰 부분은 무시되는 것을 알 수 있다. 그러면 스택에서 6, 5를 차례로 빼주면서 6을 포함해서 만들 수 있는 최대 넓이, 5를 포함해서 만들 수 있는 최대 넓이를 계산하면 된다.

현재 스택의 top보다 크거나 같은 높이가 나온다면 계속 스택에 추가하고 더 작은 높이가 나타나면 스택에서 더 큰 값들을 계속 빼가면서 계산해주면 된다. 스택의 top에는 자신 보다 작거나 같은 높이의 인덱스가 들어가게 된다. 즉 i에서 스택의 top까지의 거리가 너비가 된다.

아래 코드에서는 코드를 간결하게 하기 위해 초기 스택에 -1을 넣어주고 heights 배열에도 0을 추가해 주었다.

Source Code

from typing import List


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0)
        stack = [-1]
        max_area = 0

        for i in range(len(heights)):
            while heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                max_area = max(max_area, h * w)
            stack.append(i)
        return max_area