Funcia
Lv.3arraymonotonic-stackstack

히스토그램 속 가장 큰 직사각형

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

너비가 1인 막대 N개가 바닥에 빈틈없이 나란히 서 있는 히스토그램이 있습니다. i번째 막대의 높이는 heights[i]입니다.

히스토그램 안에 완전히 들어가는 직사각형 중 넓이가 가장 큰 것의 넓이를 반환하세요. 직사각형의 변은 바닥과 평행하거나 수직이어야 하고, 아래 변은 바닥에 붙어 있어야 합니다.

즉 연속한 구간 [l, r]를 골라 (r - l + 1) × min(heights[l..r])의 최댓값을 구하면 됩니다.

입출력 예

heightsresult
[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

제한 사항

  • 1≤N=1 \le N = heights.length ≤500,000\le 500{,}000
  • 0≤0 \le heights[i] ≤109\le 10^9
  • 답은 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비트 정수로 계산하세요.

복잡도 목표

막대마다 양쪽으로 직접 넓혀 보는 O(N2)O(N^2) 풀이는 효율성 테스트에서 시간 초과가 납니다. 각 막대가 스택에 한 번 들어가고 한 번 나오므로 O(N)O(N)입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251082 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.