FENCE (중, p. 195)
조금 고민을 하긴 했지만, 그래도 다 푸는데 1시간이 안걸렸다. (25분쯤 걸린듯)
뭔가 이런 문제는 왼쪽에서 오른쪽으로 이동하면서 현재 판자로 구할 수 있는 최대 직사각형 넓이를 구할 수 있을 것 같았다. 그리고 잘 생각해보니 답은 분명 최소 1개의 판자 전체를 포함할 것이다. 그러니 현재 보고있는 판자를 다 포함하는 최대 직사각형 넓이를 O(1)에 알 수 있도록 왼쪽에서 오른쪽으로 sweepping하면서 바로바로 계산할 방법을 찾아봤다.
또 좀 더 생각해보니 어느 시점의 판자 크기가 이전(왼쪽) 판자 보다 작아졌다면, 위에서 sweepping 알고리즘(?)을 쓸 때 방금 전 작아진 판자보다 컸었던 판자는 고려할 필요가 없을 것이다. 그래서 stack에 판자가 오름차순으로만 쌓이게 만들었다. 만약 top()의 판자보다 낮은 판자가 나오면, 낮은 판자보다 더 낮은 판자가 있기까지 계속 pop을 해준다. 이렇게 했을때 top()에 남은 판자의 index와 현재 가리키고 있는 판자의 index의 차이가 곧 현재 판자 전체를 포함하는 최대 직사각형의 왼쪽 넓이 부분을 너비를 뜻하게 된다. 따라서 여기에 현재 판자의 높이만 곱하면 현재 판자를 포함하는 최대 직사각형의 왼쪽 넓이를 구할 수 있게 된다.
이렇게 2만개의 판자에 대해 왼쪽 최대직사각형 넓이를 다 구한 뒤, 반복문을 거꾸로 돌아 오른쪽 최대 직사각형의 넓이를 구해서 더하면 각 판자별 최대 직사각형 넓이를 O(N)에 구할 수 있다.
이제 이중 가장 큰 직사각형 넓이를 출력하면 된다.
#include <bits/stdc++.h>
using namespace std;
struct Info {
int h, idx;
Info() {}
Info(int h, int idx):h(h),idx(idx) {}
bool operator<(const Info & rhs) const {
if(h == rhs.h) return idx < rhs.idx;
else return h<rhs.h;
}
};
vector<Info> st;
void Init() {
st.clear();
st.emplace_back(-1,0);
}
int h[20002];
int ans[20002];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int tc; cin >> tc;
while(tc--) {
Init();
int N; cin >> N;
for(int i=1; i<=N; i++) {
cin >> h[i];
}
for(int i=1; i<=N; i++) {
while(h[i] <= st.back().h) {
st.pop_back();
}
ans[i] = (i-st.back().idx)*h[i];
st.emplace_back(h[i], i);
}
st.clear();
st.emplace_back(-1,N+1);
for(int i=N; i>=1; i--) {
while(h[i] <= st.back().h) {
st.pop_back();
}
ans[i] += (st.back().idx-i-1)*h[i];
st.emplace_back(h[i],i);
}
int mx_ans = 0;
for(int i=1; i<=N; i++) {
mx_ans = max(mx_ans, ans[i]);
}
printf("%d\n", mx_ans);
}
return 0;
}