히스토그램에서 가장 큰 직사각형
플래티넘 V의견: 0
\(N\)개의 직사각형 막대가 가로로 나란히 붙어 있는 히스토그램이 있다. 각 막대의 너비는 \(1\)로 모두 같고, \(i\)번째 막대의 높이는 \(h_i\)이다.
이 히스토그램 안에 들어가는 축에 평행한 직사각형 중에서 넓이가 가장 큰 직사각형의 넓이를 구하여라. 직사각형의 밑변은 연속한 막대들 위에 놓여야 하며, 그 높이는 해당 구간의 막대들 중 가장 낮은 막대의 높이를 넘을 수 없다.
즉, 어떤 구간 \([l, r]\)을 골랐을 때 그 구간에서 만들 수 있는 직사각형의 넓이는 \(\left(\min_{l \le i \le r} h_i\right) \times (r - l + 1)\)이며, 이 값의 최댓값을 출력하면 된다.
\(1 \le N \le 100\,000\), \(0 \le h_i \le 10^9\).
첫째 줄에 막대의 개수 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(h_1, h_2, \dots, h_N\)이 공백으로 구분되어 주어진다.
히스토그램 안에 들어가는 가장 큰 직사각형의 넓이를 한 줄에 출력한다.
6
2 1 5 6 2 3
10
높이 \(5, 6\)인 두 막대를 묶으면 높이 \(5\), 너비 \(2\)로 넓이 \(10\)이 되어 최대이다.
3
4 4 4
12
세 막대의 높이가 모두 같으므로 \(4 \times 3 = 12\)가 최대이다.
riseoj 작성
출처 Original
평가 및 의견
히스토그램에서 가장 큰 직사각형
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
히스토그램에서 가장 큰 직사각형