https://www.acmicpc.net/problem/6549
스택 내부의 막대들은 항상 비내림차순으로 유지된다.
stack.top 막대의 높이를 Ht라 할 때, 다음 막대의 높이가 Ht보다 낮다면, Ht를 높이로 가지는 직사각형의 면적은 더이상 오른쪽으로 확장될 수 없다.
이 말이 무슨 말일까?
x축 좌표위에 직사각형이 존재한다고 가정하자. 해당 직사각형은 왼쪽 끝과 오른쪽 끝을 가질 것이다. 왼쪽 끝은 Left, 오른쪽 끝은 Right라고 부른다.
직사각형 밑변의 길이, 즉, 너비는 Right - Left가 될 것이다.
이 문제에서는 직사각형이 인덱스 축 위에 존재한다. stack.top 막대가 어떤 인덱스 i 위에 배치되어있다고 가정하자. 그리고 Ht보다 낮은 막대가 그 옆으로 배치된다.
이때, Ht를 높이로 가지는 직사각형의 Left와 Right는 무엇일까?
Left(왼쪽 경계)는 현재 top 막대를 pop하고 새로이 top이 되는 막대의 인덱스,
Right(오른쪽 경계)는 높이가 Ht보다 처음으로 낮아지는 막대의 인덱스가 될 것이다.
Left ~ Right(양 끝 제외) 범위 내의 막대들은 높이가 Ht 이상이므로
Left가 너비의 시작점이고, 높이가 Ht인 직사각형의 면적은 Right를 따라서 연속적으로 확장될 가능성이 있지만
Ht보다 낮은 막대가 배치된다면 Left + 1을 너비의 시작점으로 가지는 높이가 Ht인 직사각형의 면적은 더이상 확장될 수 없고 '확정'된다.
이때, 직사각형의 너비는 Right - Left - 1로 구해진다.
예를 들어, 3,6,9,4,2 를 높이로 가지는 막대 5개가 있다고 하자.
스택의 3, 6, 9 (인덱스는 0, 1, 2) 막대는 본인의 높이 h를 가지는 직사각형의 면적을 확장 중이다. 이때, 4 막대가 들어오면 6, 9 막대는 더이상 각각 6과 9를 높이로 가지는 직사각형의 면적을 확장할 수 없고 확정된다.
9 막대를 pop하면 6 막대가 top이 되며, 6 막대의 인덱스는 1이고 Left로 사용한다. 4 막대의 인덱스는 3이며 Right로 사용한다.
Right - Left - 1 = 1이므로 높이가 9인 직사각형의 너비 1을 구할 수 있으며 넓이는 1 * 9 = 9가 된다.
4 막대는 여전히 6 막대보다도 낮다. 6 막대를 pop하면 3 막대가 top이 되며, 3막대의 인덱스는 0이고 Left로 사용한다. 4 막대의 인덱스는 3이며 Right로 사용한다.
Right - Left - 1 = 2이므로 높이가 6인 직사각형의 너비 2를 구할 수 있으며 넓이는 2 * 6 = 12가 된다.
4 막대는 3 막대보다는 높기 때문에 더이상 위의 넓이 확정 시퀀스는 진행되지 않고, stack에 4 막대가 push되어 [3, 4]가 된다.
이때, 2 막대가 들어오면 3, 4 막대 모두 직사각형의 면적을 확장할 수 없고 확정된다.
4 막대를 pop하면 3막대가 top이 되며, 3막대의 인덱스는 0이고 Left로 사용한다. 2 막대의 인덱스는 4이며 Right로 사용한다.
Right - Left - 1 = 3이므로 높이가 4인 직사각형의 너비 3을 구할 수 있으며 넓이는 3 * 4 = 12가 된다.
3 막대의 경우, pop하면 스택이 완전히 비게된다. 이때의 너비는 Right가 된다.(Left를 -1로 간주하면 된다.) 높이 3인 직사각형의 너비는 4고, 넓이는 4 * 3 = 12가 된다.
그 후 2를 push 한 뒤, 더이상 새로운 막대가 존재하지 않으므로 스택에 남은 막대인 2가 만드는 직사각형에 대한 넓이를 계산해준다.
이때, 즉, 입력이 끝난 경우 인덱스가 n이고 높이는 0인 가상의 막대를 스택에 추가로 집어 넣는다고 생각하면 편하다.
이러면 스택에 남은 실제 막대들의 넓이는 (n - left - 1) * H 로 계산하며 마감 가능하다.
문제 풀이는 스택에 index를 push하는 방법 또는 (height, index) 페어를 push하는 방법이 존재하며, 스택 외에도 세그먼트 트리를 이용한 풀이도 존재한다.
#include <iostream>
#include <stack>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
while (1) {
cin >> n;
if (n == 0) break;
stack<pair<int,int>> s;
long long ans = 0;
for (int i = 0; i < n; i++) {
int curr_height;
cin >> curr_height;
while (!s.empty() && s.top().first > curr_height) {
long long top_height = s.top().first;
s.pop();
int left;
int right = i;
if (s.empty())
left = -1;
else
left = s.top().second;
long long area = (right - left - 1) * top_height;
ans = max(ans, area);
}
s.push(make_pair(curr_height, i));
}
while (!s.empty()) {
long long top_height = s.top().first;
s.pop();
int left;
int right = n;
if (s.empty())
left = -1;
else
left = s.top().second;
long long area = (right - left - 1) * top_height;
ans = max(ans, area);
}
cout << ans << "\n";
}
}또는
#include <iostream>
#include <stack>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
while (1) {
cin >> n;
if (n == 0) break;
stack<pair<int,int>> s;
long long ans = 0;
for (int i = 0; i <= n; i++) {
int curr_height;
if (i == n)
curr_height = 0;
else
cin >> curr_height;
while (!s.empty() && s.top().first > curr_height) {
long long top_height = s.top().first;
s.pop();
int left;
int right = i;
if (s.empty())
left = -1;
else
left = s.top().second;
long long area = (right - left - 1) * top_height;
ans = max(ans, area);
}
s.push(make_pair(curr_height, i));
}
cout << ans << "\n";
}
}