히스토그램 속 가장 큰 직사각형
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
너비가 1인 막대 N개가 바닥에 빈틈없이 나란히 서 있는 히스토그램이 있습니다. i번째 막대의 높이는 heights[i]입니다.
히스토그램 안에 완전히 들어가는 직사각형 중 넓이가 가장 큰 것의 넓이를 반환하세요. 직사각형의 변은 바닥과 평행하거나 수직이어야 하고, 아래 변은 바닥에 붙어 있어야 합니다.
즉 연속한 구간 [l, r]를 골라 (r - l + 1) × min(heights[l..r])의 최댓값을 구하면 됩니다.
입출력 예
| heights | result |
|---|---|
[2, 1, 5, 6, 2, 3] | 10 |
[2, 4] | 4 |
[3, 3, 3, 0, 1] | 9 |
입출력 예 설명
예 1 — 높이 5, 6인 두 막대에 걸친 높이 5, 너비 2의 직사각형이 넓이 10으로 가장 큽니다.
예 2 — 높이 4인 막대 하나(넓이 4)가 두 막대 전체에 걸친 높이 2짜리(넓이 4)와 같습니다.
예 3 — 앞의 세 막대에 걸친 높이 3, 너비 3의 직사각형입니다. 높이 0인 막대는 직사각형을 끊습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(heights: int[]) → long
제한 사항
-
heights.length -
heights[i] - 답은 32비트 정수를 넘을 수 있습니다.
기대 복잡도
- 시간
- O(N)
- 공간
- O(N)
입출력 예
| heights | 기대 출력 |
|---|---|
[2,1,5,6,2,3] | 10 |
[2,4] | 4 |
[3,3,3,0,1] | 9 |
힌트
힌트
가장 큰 직사각형의 높이는 반드시 어떤 막대 i의 높이와 같습니다. 막대 i의 높이를 쓰는 직사각형은
왼쪽·오른쪽으로 heights[i]보다 낮은 막대를 만나기 직전까지 넓힐 수 있습니다.
그래서 막대마다 "왼쪽에서 처음 만나는 더 낮은 막대"와 "오른쪽에서 처음 만나는 더 낮은 막대"를 알면 됩니다. 이것을 높이가 증가하는 순서를 유지하는 스택으로 한 번에 구할 수 있습니다.
왼쪽부터 막대를 보며, 스택 맨 위 막대가 지금 막대보다 높거나 같으면 꺼냅니다. 꺼낸 막대 j에 대해
오른쪽 경계는 지금 위치, 왼쪽 경계는 꺼낸 뒤의 스택 맨 위이므로 그 자리에서 넓이를 계산할 수 있습니다.
마지막에 높이 0인 막대를 하나 더 넣으면 남은 막대도 모두 처리됩니다.
넓이는 64비트 정수로 계산하세요.
복잡도 목표
막대마다 양쪽으로 직접 넓혀 보는 풀이는 효율성 테스트에서 시간 초과가 납니다. 각 막대가 스택에 한 번 들어가고 한 번 나오므로 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1082 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 4 | 판정만 |