LeetCode 84: 히스토그램에서 가장 큰 사각형 — 단계별 시각적 추적

Source: Dev.to

Problem

히스토그램을 나타내는 막대 높이 배열에서 만들 수 있는 가장 큰 직사각형의 넓이를 찾으세요. 각 막대의 너비는 1이며, 직사각형은 연속된 막대로 이루어져야 합니다.

Approach

단조 스택을 사용하여 높이가 증가하는 순서대로 막대의 인덱스를 추적합니다. 더 짧은 막대를 만나면, 이전에 저장된 더 높은 막대들을 높이로 사용하여 직사각형을 계산하고, 너비는 현재 위치와 스택 내용에 따라 결정합니다.

Complexity

• 시간: (O(n))
• 공간: (O(n))

Code

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

        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)

        while stack:
            height = heights[stack.pop()]
            width = len(heights) if not stack else len(heights) - stack[-1] - 1
            max_area = max(max_area, height * width)

        return max_area