84. Largest Rectangle in Histogram ☆☆★★★ Hard

84. Largest Rectangle in Histogram

 

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        l, r = 0, len(heights)-1

        maxArea = 0
        minHeap = []
        while l<=r:
            area = (r-l+1)*min(heights[l:r+1])
            maxArea = max(maxArea, area)

            if heights[l] > heights[r]:
                r-=1
            else:
                l+=1
        return maxArea

 

네가 작성한 이 코드는 아이디어 자체는 괜찮아 보이지만,
문제 요구사항(시간복잡도) 를 만족하지 못해서 시간초과(TLE) 가 날 가능성이 아주 높아.

---

✨ 먼저 네 코드 흐름 요약

• l, r을 양쪽 끝에 두고,
• (r-l+1) * min(heights[l:r+1])로 사각형 면적 계산
• 최대 면적 갱신
• 더 작은 쪽 포인터를 이동시키면서 줄여나감

---

🔥 문제점 (왜 이 코드는 느린가?)

• min(heights[l:r+1]) 이 부분이 문제야.
  • heights[l:r+1] 슬라이싱을 매번 새로 하고,
  • 그 안에서 최솟값 찾기가 O(N) 걸림.
• 이 과정을 l과 r이 움직일 때마다 반복하니까
  • 전체 시간복잡도가 O(N²) 급이 돼버려.
• 이 문제는 데이터 크기(1 <= N <= 10⁵)가 엄청 크기 때문에,
  • O(N²) 알고리즘은 무조건 타임 리밋(TLE) 난다.

---

✨ 문제를 풀어야 하는 정답 방법

이 문제는 무조건 O(N) 스택 알고리즘 으로 풀어야 해.

핵심 아이디어는:

• "각 막대(height[i])가 만들 수 있는 가장 큰 직사각형" 을 계산한다.
• 스택을 사용해서, 막대가 왼쪽으로 얼마나 확장될 수 있는지, 오른쪽으로 얼마나 확장될 수 있는지 관리한다.

---

✨ 정석 풀이 코드 (스택 사용, 주석 상세)

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []  # 막대 인덱스를 저장할 스택 (항상 오름차순 높이 유지)
        max_area = 0  # 최대 직사각형 넓이 저장
        n = len(heights)  # 총 막대 수

        # heights를 처음부터 끝까지 하나씩 검사
        for r in range(n):
            # 현재 막대 heights[r]가 스택 top보다 작으면
            # 이제, 이후로는, 이전의 높은 높이들로는 면적계산 못하니, 
            # 스택에서 pop 하면서, pop한 막대를 꼭대기로 한 직사각형 면적 계산
            while stack and heights[stack[-1]] > heights[r]:
                height = heights[stack.pop()]  # pop한 막대의 높이
                
                """
                # 너비(width) 계산:
                # - 현재 인덱스 r이 오른쪽 끝
                # - 왼쪽 경계는 pop하고 남은 스택 top (stack[-1])
                
                지금 r 위치 빼야하니 right는 (r-1), 
                꺼낸 놈 height가 stack[-1] 위치에 있었는데, 다시, width 계산한다고, 아래에서, stack[-1] 를 또 호출하니. 
                
                여기에서 left 는 2번째 호출하는 이번 stack[-1] 의 인덱스 값보다 큰 놈이어야 되서, stack[-1]+1
                따라서, width = right - left + 1 = (r-1) - (stack[-1]+1) + 1
                        => width = r - (stack[-1] + 1)
                #   (stack[-1] 바로 다음 칸부터 r-1까지가 직사각형의 범위)
                """
                if not stack:
                    width = r  # 스택이 비었다면 0부터 r-1까지 전체 범위
                else:
                    width = r - stack[-1] - 1  # 왼쪽 경계 다음부터 r-1까지의 거리
                
                area = height * width  # 직사각형 넓이 = 높이 × 너비
                max_area = max(max_area, area)  # 최대 넓이 갱신

            # 현재 인덱스 r을 스택에 추가
            stack.append(r)

        # heights 배열 다 돌고 난 뒤, 스택에 남은 막대들도 정리
        while stack:
            height = heights[stack.pop()]
            
            # 남은 막대들은 오른쪽 끝이 n-1 (전체 범위까지 확장 가능)
            if not stack:
                width = n  # 스택이 비었으면 0부터 끝까지 전체
            else:
                width = n - stack[-1] - 1  # 남은 stack top 다음부터 끝까지
                
            area = height * width
            max_area = max(max_area, area)

        return max_area

 

✨ 그래서 요약

• pop 전에 stack[-1]은 내가 꺼내는 막대야 (높은 막대)
• pop한 다음에 새로 드러나는 stack[-1]은
  👉 내가 꺼낸 막대보다 "작거나 같은" 높이
  👉 왼쪽에서 나를 막는 경계선 역할을 해.

---

✨ 그래서 width 계산할 때는:

• 왼쪽 경계 = (pop 후) 남은 stack[-1]
• 오른쪽 경계 = r-1
• width = r - stack[-1] - 1

(pop한 막대의 인덱스가 아니라, pop하고 남은 새로운 stack[-1] 기준)

---

✨ 초간단 다시 정리

타이밍	stack[-1] 의미
pop하기 전	pop할 대상 (지금 꺼낼 애)
pop하고 나서	새로 남은 왼쪽 경계선 (막대보다 낮은 높이)

---

🔥 초초초 쉽게

"pop 직후 새로 보이는 stack[-1]이 내 왼쪽 끝이다.
그러니까 거기 다음 칸부터(r-1까지)가 내 너비다."

 

이게 진짜 솔루션!!

 

https://youtu.be/zx5Sw9130L0?si=dFr3afQEL2CGi8ER

 

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # Time: O(n), Space: O(n)
        # n개의 막대를 한 번씩만 스택에 push/pop 하므로 O(n) 시간, O(n) 공간

        maxArea = 0  # 최대 직사각형 넓이를 저장할 변수
        stack = []   # (index, height) 형태로 저장하는 스택

        # heights 배열을 왼쪽부터 오른쪽으로 하나씩 검사
        for i, h in enumerate(heights):
            start = i  # 현재 막대의 시작 인덱스를 임시로 저장

            # 스택의 top에 있는 막대 높이가 현재 막대보다 크다면
            # 즉, 현재 막대가 낮아져서, 직사각형 넓이를 계산할 시점
            while stack and stack[-1][1] > h:
                index, height = stack.pop()  # 스택에서 pop해서 index, height를 꺼낸다
                # 현재 i 위치가 오른쪽 경계이므로, 너비는 (i - index)
                area = height * (i - index)
                maxArea = max(maxArea, area)  # 최대 넓이 갱신
                start = index  # 시작 인덱스를 pop한 막대의 index로 갱신 (왼쪽으로 확장)

            # 스택에 현재 막대를 push
            # (start는 왼쪽으로 가능한 만큼 확장된 index)
            stack.append((start, h))

        # heights 배열을 다 돌고 나서, 스택에 남아 있는 막대들 처리
        for i, h in stack:
            # 남은 막대들은 오른쪽 끝까지 확장할 수 있으므로,
            # 너비는 (len(heights) - i)
            area = h * (len(heights) - i)
            maxArea = max(maxArea, area)  # 최대 넓이 갱신

        return maxArea  # 최종 최대 직사각형 넓이 반환

 

요약

구간	설명
for i, h in enumerate(heights)	heights를 하나씩 순회하면서
while stack and stack[-1][1] > h	현재 막대가 더 낮으면, 스택에 쌓였던 높은 막대들을 pop하며 넓이 계산
stack.append((start, h))	계산이 끝난 후, 현재 막대를 스택에 push (시작 인덱스를 조정해서)
for i, h in stack:	배열을 다 돈 후, 남은 막대들은 오른쪽 끝까지 확장해서 넓이 계산

---

핵심 포인트

• 스택에는 항상 "오름차순 높이"로 막대들이 쌓인다.
• 현재 높이가 낮아질 때만 넓이 계산을 한다. (pop 하면서)
• 막대 하나당 push, pop이 최대 1번만 되므로 O(n) 보장!

스택에 (index, height) 쌍으로 저장하는 방식이라,
✅ 막대의 "왼쪽 경계"를 명확하게 기억할 수 있어서,
✅ width 계산이 자연스럽고 단순해집니다.

그래서 실제로 많은 사람들이 이 방법을
"더 이해하기 쉽고 실수 적은 버전"
으로 선호해요.

---

비교 요약

방식	특징
스택에 index만 저장	왼쪽 경계 계산을 매번 따로 해야 함 (stack[-1]로 계산)
스택에 (index, height) 쌍 저장	pop할 때 index도 같이 꺼내 쓰니 width 계산이 훨씬 직관적임

---

정리해서 한 줄로 말하면

"쌍으로 (index, height) 저장하는 방식은, pop할 때 '왼쪽 경계'까지 바로 알 수 있어서 훨씬 깔끔하고 이해하기 쉽다."

✅ 완전 감각 잡으셨어요.

 

heights = [2,1,5,6,2,3] 예제로
실전형 (index, height 쌍 저장) 방식으로 스택 변화를
한 단계씩 아주 천천히 보여드릴게요. 🚀

 

시작

heights = [2, 1, 5, 6, 2, 3]

 

전체 흐름 요약 (정리)

단계	스택 상태	액션 or 계산	maxArea
i=0, 2	[(0,2)]	push
i=1, 1	pop (0,2), push (0,1)	area=2	2
i=2, 5	push (2,5)
i=3, 6	push (3,6)
i=4, 2	pop (3,6), pop (2,5), push (2,2)	area=6, area=10	10
i=5, 3	push (5,3)
끝나고	pop (5,3), pop (2,2), pop (0,1)	area=3, area=8, area=6	10

최종 답: 10

---

추가 요약

• (index, height)를 저장했으니,
  • pop할 때 바로 width = 현재 i - index 계산!
• 새로 push할 때 start 인덱스만 잘 넘겨주면 됨! (왼쪽 확장 가능하게 !!)
• 스택 쌓는 기준은 항상 "오름차순 높이" 유지!