[BOJ 6549] 히스토그램에서 가장 큰 직사각형

알고리즘 분류: 자료구조, 분할정복, 세그먼트트리, 스택

비슷한 문제: BOJ 1725, 히스토그램

 

이중 스택을 이용한 풀이가 잘 알려져 있고, 이 때의 시간복잡도는 $O(2N) = O(N)$이다.

 

핵심 아이디어

(1) 히스토그램의 높이가 증가할 때 까지 스택에 인덱스를 push 한다

(2) 히스토그램의 높이가 감소한다면

    (2.1) 현대 인덱스는 i, 직전의 히스토그램의 인덱스는 stack.top 일 것 이다

    (2.2) 스택이 비워질 때 까지 인덱스를 pop하면서 현재 넓이를 구한다

    (2.3) 이때 width = (i - top - 1), height = H[stack.top] 이 된다

(3) 스택이 비어있지 않다면, 히스토그램의 마지막 부분이 증가하다가 끝난 경우이다

    (3.1) (2)의 과정을 한 번 더 반복한다

 

 

그림으로 아이디어 이해

(좌) 일반적인 넓이 탐색 케이스 (가운데) 감소하는 경우 (우) 스택이 비워지지 않은 경우는, 히스토그램이 증가한 상태로 끝난 경우이다

 

소스코드

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void IOSetup();

int N;

int main() {
    IOSetup();

    while (1) {
        // input
        cin >> N;
        if (N == 0) break;

        vector<int> H(N);
        for (int i = 0; i < N; i++) { cin >> H[i]; }

        // solve
        stack<int> stk;
        long long curW, curH, curArea;
        long long maxArea = 0;

        for (int i = 0; i < N; i++) {
            // H[i] < H[top] -> compute / update the area
            while (!stk.empty() && H[stk.top()] > H[i]) {
                curW = i;
                curH = H[stk.top()];
                stk.pop();

                if (!stk.empty()) curW = i - stk.top() - 1;
                curArea = curW * curH;
                maxArea = max(maxArea, curArea);
            }
            stk.push(i);
        }

        while (!stk.empty()) {
            curW = N;
            curH = H[stk.top()];
            stk.pop();

            if (!stk.empty()) curW = N - stk.top() - 1;
            curArea = curW * curH;
            maxArea = max(maxArea, curArea);
        }
        cout << maxArea << "\n";
    }

    return 0;
}

void IOSetup() {
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

 

후기

스택을 이용한 알고리즘은 발상을 떠올리기 쉽지 않은 것 같다

예를 들면 뒤에서부터 생각하기 라든지, 히스토그램처럼 스택에 인덱스를 넣고 비교한다든지...