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

문제

문제 바로가기> BOJ 6549번: 히스토그램에서 가장 큰 직사각형

6549번: 히스토그램에서 가장 큰 직사각형

 

풀이

스택을 이용하여 O(N)만에 정답을 구할 수 있다.

낮아지는 경우와 높아지는 경우로 구분하고, 낮아지는 경우에 pop한 idx를 현재 높이와 함께 다시 스택에 넣어주는 부분이 핵심인듯 하다!! 

#include<iostream>
#include<stack>
#define MAX 100005
using namespace std;

struct DATA{int idx; long long h;};

int N; //히스토그램수
int H[MAX]; //히스토그램 높이

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

long long getMaxArea(){ // 히스토그램에서 가장 큰 직사각형의 넓이
    long long res=0, ph;
    int pidx = 0;
    
    stack<DATA> s; // 직사각형을 그릴 수 있는 정보 저장
    for(int idx=0; idx<=N; idx++){
        bool is_low = false;
        while(!s.empty() && (idx == N || s.top().h > H[idx])){ // 히스토그램 끝 처리 및 낮아지는 경우
            pidx = s.top().idx;
            ph = s.top().h;
            is_low = true;
            res = max(res, (idx-pidx)*ph); // 계산하고
            s.pop(); // 제거
        }
        if(is_low && idx < N) s.push({pidx, H[idx]}); // 낮아지는 경우
        else s.push({idx, H[idx]}); // 같거나 높아지는 경우
    }

    return res;
}

void solve(){
    while(true){ // 여러 개의 TC
        cin >> N;
        if(N == 0) break; // 종료 조건
        input();
        cout << getMaxArea() << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
}