히스토그램

Disjoint Set Union(dsu)

출처: BOJ 히스토그램

sol)
양 옆으로 어디까지 갈 수 있는지 계산하여 넓이를 구한다.


[-] Collapse

#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;

pair<int, int> h[100002];
int ori[100002];
int isMerge[100002];
int par[100002];

bool comp(pair<int, int> l, pair<int, int> r){
    if (l.first < r.first) return false;
    else if (l.first == r.first){
        if (l.second > r.second) return false;
        else return true;
    }
    else return true;
}
int find(int idx){
    if (par[idx] == idx) return idx;
    else return par[idx] = find(par[idx]);
}
void merge(int l, int r){
    l = par[l], r = par[r];
    par[r] = l;
}

int main(){
    //freopen("input.txt", "r", stdin);
    memset(isMerge, -1, sizeof(isMerge));
    int n; scanf("%d", &n);
    int ans = 0;
    h[0].first = h[n + 1].first = 0;
    for (int i = 0; i < 100002; i++) par[i] = i;
    for (int i = 1; i <= n; i++){
        scanf("%d", &h[i].first);
        ori[i] = h[i].first;
        h[i].second = i;
    }

    sort(h + 1, h + n + 1, comp);

    for (int i = 1; i <= n; i++){
        int height = h[i].first;
        int idx = h[i].second;
        int can = 1;
        if (isMerge[idx - 1] != -1 && height <= ori[idx-1]){
            can += isMerge[find(idx - 1)];
            merge(idx, idx - 1);
        }
        if (isMerge[idx + 1] != -1 && height <= ori[idx+1]){
            can += isMerge[find(idx + 1)];
            merge(idx, idx + 1);
        }
        isMerge[idx] = can;
        if (ans < height *can) ans = height *can;
    }
    printf("%d", ans);
    return 0;
}