카테고리 없음
Stack #1 -
cepiloth
2019. 8. 30. 08:05
반응형
- 유용한 설명과 문제 풀이
https://www.acmicpc.net/blog/view/12
#include <cstdio>
#include <stack>
using namespace std;
int a[100000];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
stack<int> s;
int ans = 0;
for (int i = 0; i < n; i++) {
int left = i;
while (!s.empty() && a[s.top()] > a[i]) {
int height = a[s.top()];
s.pop();
int width = i;
if (!s.empty()) {
width = (i - s.top() - 1);
}
if (ans < width*height) {
ans = width * height;
}
}
s.push(i);
}
while (!s.empty()) {
int height = a[s.top()];
s.pop();
int width = n;
if (!s.empty()) {
width = n - s.top() - 1;
}
if (ans < width*height) {
ans = width * height;
}
}
printf("%d\n", ans);
return 0;
}
반응형