[LeetCode] 84. Largest Rectangle in Histogram

84. Largest Rectangle in Histogram

Hard

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

 

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

 

Constraints:

• 1 <= heights.length <= 105
• 0 <= heights[i] <= 104

---

문제 풀이

• 히스토그램에서 만들 수 있는 직사각형 중 가장 큰 크기를 가진 직사각형의 너비를 찾는 문제이다. 
• 배열에 각 히스토그램 막대의 길이가 주어진다. 
• 막대 하나의 길이는 1이고 직사각형은 막대들이 연속으로 있을때 같은 높이로 잘라 만들 수 있다.
• 예를들어, 5, 6이 있다면 막대 두개의 너비 2와 높이 5로 직사각형을 만들 수 있다. 
• 스택을 사용하면 시간 복잡도 O(N)으로 문제를 풀 수 있다. 
• 우선 스택에 -1 더미 값을 넣는다. 
• 더미 값이 없다면 막대가 하나만 남았을때 너비 계산을 할 수 없다.
• 막대를 하나씩 스택에 넣되, 스택에 들어갈 수 있는 막대는 이전막대보다 커야한다. 
• 만일 작은 막대가 등장한다면 스택에 있는 높이를 빼서 직사각형의 너비를 계산해 준다. 
• 즉, 오름차순으로 스택에 계속해서 넣으면서 너비를 늘려간다. 
• 높이를 계산할때는 이미 스택에 들어있는 막대의 크기는 크기 순으로 정렬되어있기 때문에, 
• 스택에서 뺀 높이 값을 높이로 정하고 현재 인덱스 위치에서 스택에서 뺀 값의 인덱스까지를 너비로 정한다.
• 즉 1, 2, 3, 4 이 스택에 들어가 있고 3이 등장한다면
• 4부터 너비를 구한다, 스택의 첫번째 pop 될 막대의 직사각형 넓이는 1 * 4 = 4
• 4가 pop되고 나서 3의 넓이는 2 * 3 = 6
• 3이 pop되고 나서 2의 넓이는 3 * 2 = 6 이런식으로 계산된다. 
• 스택에는 항상 오름차순으로 막대의 높이가 들어가고, 작은 숫자가 나타나면 스택에서 값들을 빼서 직사각형의 너비를 조절하기 때문에
• 스택에 들어있는 막대의 높이는 항상 최소 값이 되어 붙어있는 막대들로 직사각형을 만들 수 있다. 
• heights에 들어있는 값을 모두 처리하고 남은 스택의 막대들도 마찬가지로 직사각형의 넓이를 구해주는데 
• 여기서는 이미 스택에 남은 막대들보다 heights의 막대들의 높이는 다 작기 때문에 heights의 전체 길이에서 직사각형의 너비를 계산해야한다.

소스 코드

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