[1스4코2파] # 184. LeetCode 84. Largest Rectangle in Histogram

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (184차)
[4코1파] 2023.01.13~ (176일차)
[1스4코1파] 2023.04.12~ (87일차)
[1스4코2파] 2023.05.03 ~ (65일차)

Today :

2023.07.06 [184일차]
LeetCode Patterns
84. Largest Rectangle in Histogram
https://leetcode.com/problems/largest-rectangle-in-histogram/

84. Largest Rectangle in Histogram

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

문제 설명

주어진 히스토그램 내에서 가장 큰 직사각형을 찾는 것(면적)

문제 풀이 방법

세로길이를 fix 해 둔 바의 인덱스를 기준으로 포함되지 않는 오른쪽 경계 인덱스를 right, 왼쪽 경계 인덱스를 left라 할 때, 가로길이는 right - left - 1 이다.

특정 인덱스 i를 포함하는 직사각형의 최대크기는 heights[i] * (right - liet - 1)
right, left 를 구할 효과적인 방법은 stack을 사용해서 2번의 선형 탐색을 통해 구한다.

내 코드

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

        for i,h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                maxArea = max(maxArea, height*(i-index))
                start = index
            stack.append((start, h))

        for i,h in stack:
            maxArea = max(maxArea, h*(len(heights) -i))
        return maxArea

증빙

여담

? 무슨 말이지 ?