백준 6549 - 히스토그램에서 가장 큰 직사각형, C++, 스택

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

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

long long n;
long long hist[100010];

int main(){
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);

    while(true){
        cin >> n;
        if(n <= 0)
            break;

        for(int i = 0; i < n; i++)
            cin >> hist[i];
        hist[n] = -1;

        stack<int> s;
        long long ans = 0;
        for(int i = 0; i <= n; i++){
            // hist[i] < hist[s.top()] && !s.empty()  => ?
            while(!s.empty() && hist[i] < hist[s.top()]){
                int height, weight;

                height = s.top();
                s.pop();

                if(s.empty())
                    weight = i;
                else 
                    weight = i - s.top() - 1;

                ans = max(ans, hist[height] * weight);
            }
            s.push(i);
        }

        cout << ans << '\n';
    }
}

---

 

백준 1725 히스토그램 - 스택을 이용한 C++

 옛날 히스토그램 문제를 푼거와 비슷하게 했습니다. 순차대로 막대를 넣는데 새로 들어오는 막대가 이전의 막대보다 작다면 사각형을 만들 수 없는걸 이용한 풀이입니다. 

 

 위에 와일문 조건 체크에서 스택이 비어있는걸 먼저 확인해샤 세그먼트 오류가 안나오는 문제였습니다. 이 오류때문에 고생좀 했습니다...