6026 : 히스토그램 최대 직사각형
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
히스토그램에 $N$개의 직사각형 막대가 나열되어 있습니다. 각 막대의 폭은 1이고 높이가 주어집니다.
이 히스토그램 내부에 그릴 수 있는 가장 넓은 직사각형의 넓이를 계산하십시오.
이 히스토그램 내부에 그릴 수 있는 가장 넓은 직사각형의 넓이를 계산하십시오.
입력 설명
첫째 줄에 막대의 개수 $N$이 주어집니다. ($1 \le N \le 100,000$)
둘째 줄에 $N$개의 막대 높이가 공백으로 구분되어 주어집니다. ($0 \le \text{높이} \le 10^9$)
둘째 줄에 $N$개의 막대 높이가 공백으로 구분되어 주어집니다. ($0 \le \text{높이} \le 10^9$)
출력 설명
히스토그램 내부 최대 직사각형의 넓이를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7
2 1 4 5 1 3 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
8도움
단조 증가 스택(Monotonic Stack)을 이용하여 각 막대가 최소 높이가 되는 경계를 $O(N)$에 탐색하여 면적의 최댓값을 구합니다.