[leetcode] 84. Largest Rectangle in Histogram

문제 설명

링크
히스토그램에서 가장 큰 사각형의 넓이를 찾는 문제

접근 - Stack

• index 를 stack 에 넣음
• for 문을 돌면서 현재 높이가 stack 의 끝보다 작으면 pop 시작
• 넓이를 갱신

코드

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