BOJ 1725 히스토그램 (2)

문제

https://www.acmicpc.net/problem/1725

히스토그램에서 얻을 수 있는 직사각형의 최대 넓이를 구하는 문제이다.

 

풀이

저번에 Divide & Conquer + Greedy 로 $O(NlogN)$ 에 푼 경험이 있는 문제 이다.

하지만 이 문제의 정해는 $O(N)$ 으로 솔브가 가능하며, 바로 스택을 사용한 라인 스위핑이다.

 

i번째 그래프에 대하여 그 그래프를 최소 높이로 가지는 직사각형은 양 끝에 h[i]보다 낮은 그래프를 가질 수밖에 없다.

이를 이용하여 $O(N^2)$ 도 가능하지만, dnc 보다도 못한 결과가 나온다.

여기서도 전에 사용했던 정보를 재활용하면 풀 수 있다.

 

만약에 아직 자신보다 높이가 낮은 오른쪽 좌표를 결정하지 못한 그래프들이 있다고 하자.

방금 새로운 그래프를 추가했을 때 그 그래프보다 높이가 높은 그래프들의 입장에서는 자신보다 오른쪽에 자신보다 낮은 높이가 등장했으므로 바로 직사각형의 넓이를 구할 수 있다. 또한, 그 그래프는 오른쪽에 더 낮은 그래프에 막혀 다른 직사각형의 왼쪽이 되지도 못한다.

따라서 걍 지워버릴 수 있다.

 

이와 같이 스위핑 알고리즘을 설계할 수 있다.

일단 스택에 아직 직사각형 넓이를 구하지 못한 그래프들을 오름차순으로 유지한다.

스택에서 자신보다 큰 그래프를 빼서 넓이를 구하고 제거한다.

자신을 추가한다.

 

이 과정을 반복하면 스택에 N개의 원소가 한번 들어가고 한번 나오기 때문에 시간복잡도는 $O(N)$이 된다.

 

시간 복잡도 : O(N)

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int n, h[MAXN+10], ans;

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    scanf("%d", &n);
    for(i=1; i<=n; i++) scanf("%d", &h[i]);
    h[0]=h[n+1]=0;

    vector<int> S;
    for(i=0; i<=n+1; i++)
    {
        while(!S.empty() && h[S.back()]>=h[i]) { int t=h[S.back()]; S.pop_back(); ans=max(ans, t*(i-S.back()-1)); }
        S.push_back(i);
    }

    printf("%d", ans);
    return 0;
}