[백준] 6549. 히스토그램에서 가장 큰 직사각형(c++)

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

 

키가 되었던 아이디어는 시작점을 바꿔주는 것이었다.

 

현재 입력값이 stack.top()보다 작을 때 쌓아왔던 큰 값들의 넓이 최댓값들을 검증해준다.

 

시작점을 바꿔주는 이유는 stack.top에 있는 값이 자기 자신보다 크니 후에 flush 할 때 곱해줄 수 있게 start_idx를 stack.top의 index를 것으로 최신화 시키는 것이다. 

 

입력값을 다 받은 후 flush도 잊지 말고 해주자.

 

---

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    while (1) {
        int n;

        cin >> n;

        if (n == 0) break;

        int input;

        long long int Max = 0;

        // 1: 높이, 2.2: 시작 인덱스
        stack<pair<int, int> > stk;

        for (int i = 0; i < n; i++) {
            cin >> input;

            // push 할 인덱스
            int push_start_idx = i;

            // flush 타임 (stack에 있는 값이 input보다 클 때)
            while (!stk.empty() && stk.top().first >= input) {

                int cal_idx = i - stk.top().second;

                // input 값은 나중에 검증하면 된다.
                Max = max(Max, 1LL * stk.top().first * cal_idx);
                // 시작점 다시 바꿔주기
                push_start_idx = stk.top().second;

                stk.pop();
            }

            stk.push(make_pair(input, push_start_idx));
        }

        while (!stk.empty()) {
            int cal_idx = n - stk.top().second;

            Max = max(Max, 1LL * stk.top().first * cal_idx);

            stk.pop();
        }

        cout << Max << "\n";
    }
    return 0;
}