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

해결방법

라인 4번 문제와 흡사한 문제로 보인다. 이상하게 요즘 문제들이 쉬운듯 어려운 문제가 많이 보이는데 여러가지 자료구조를 안써보았기 때문이라고 생각한다. 무작위로 풀면서 사고력을 길러야 겠다. 내가 푼 방법은 2가지 이다. segment tree + conqure & divide방법과 stack방법이다.

Segment Tree + conquare & divide

Segment Tree는 각 구간에서 가장 높이가 낮은 index를 저장해준다.

int init(int leftn, int rightn, int node) {
  if (leftn == rightn) return tree[node] = leftn;
    int mid = (leftn + rightn) / 2;
    int leftv = init(leftn, mid, 2 * node);
    int rightv = init(mid + 1, rightn, 2 * node + 1);
  return tree[node] = n[leftv] < n[rightv] ? leftv : rightv;

Conquare&divide방법으로는 재귀 방식으로 넓이를 구하는 데에 사용하였다.
구간 내에서 가장 최소 높이(m번째)를 찾아 넓이를 구한다.
if (start >= m + 1) start부터 m+1사이 중 최소 높이를 찾아 넓이를 구해 리턴
if (end <= m - 1) m - 1부터 end사이 중 최소 높이를 찾아 넓이를 구해 리턴

  ll largest(RMQ r, ll start, ll end) {
    int m = r.query(0, N - 1, start, end, 1);
    ll ret = (end - start + 1) * n[m];
    if (start <= m - 1)
        ret = max(ret, largest(r, start, m - 1));
    if (end >= m + 1)
        ret = max(ret, largest(r, m + 1, end));
    return ret;
  }

스택

스택에는 높이 대신에 index번호를 저장한다. 만약 스택의 최고높이보다 낮은 높이가 들어온다면
while ( n[st.top()] > 다음 높이 ) ans = max(ans, h*w) 하여 주고 마지막 index까지
마지막에 스택이 비어있지 않다면 비어있을 때까지 위의 과정을 반복한다.

전체소스

STACK

#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long ll;
int n[100000 + 1], N;
int main() {
    while (true) {
        cin >> N;
        if (N == 0) break;
        stack<ll> st;
        ll ans = 0;
        for (int i = 0; i < N; ++i) {
            cin >> n[i];
            while (!st.empty() && n[st.top()] > n[i]) {
                int h = n[st.top()];
                int w = i;
                st.pop();
                if (!st.empty())
                    w = i - st.top() - 1;
                ans = max(ans, (ll) h*w);
            }
            st.push(i);
        }
        while (!st.empty()) {
            int h = n[st.top()];
            int w = N;
            st.pop();
            if (!st.empty())
                w = N - st.top() - 1;
            ans = max(ans, (ll)h * w);
        }
        cout << ans << endl;
    }
    return 0;
}

Segment Tree + Conquare & divide

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
ll n[100000 + 1];
int N = 1;
struct RMQ {
    vector<int> tree;
    RMQ(int n) {
        tree.resize(4*n);
        init(0, n - 1, 1);
    }
    int init(int leftn, int rightn, int node) {
        if (leftn == rightn) return tree[node] = leftn;
        int mid = (leftn + rightn) / 2;
        int leftv = init(leftn, mid, 2 * node);
        int rightv = init(mid + 1, rightn, 2 * node + 1);
        return tree[node] = n[leftv] < n[rightv] ? leftv : rightv;
    }
    int query(int leftn, int rightn, int left, int right, int node) {
        if (leftn > right || rightn < left) return -1;
        if (leftn >= left && right >= rightn)
            return tree[node];
        int mid = (leftn + rightn) / 2;
        int leftv = query(leftn, mid, left, right, 2 * node);
        int rightv = query(mid + 1, rightn, left, right, 2 * node + 1);
        if (leftv == -1)
            return rightv;
        if (rightv == -1)
            return leftv;
        return n[leftv] < n[rightv] ? leftv : rightv;
    }
};
ll largest(RMQ r, ll start, ll end) {
    int m = r.query(0, N - 1, start, end, 1);
    ll ret = (end - start + 1) * n[m];
    if (start <= m - 1)
        ret = max(ret, largest(r, start, m - 1));
    if (end >= m + 1)
        ret = max(ret, largest(r, m + 1, end));
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(0), cin.tie(0);
    while (true) {
        cin >> N;
        if (N == 0)
            break;
        for (int i = 0; i < N; ++i)
            cin >> n[i];
        RMQ tree(N);
        cout << largest(tree, 0, N - 1) << '\n';
    }
    return 0;
}