[BOJ] 1725. 히스토그램

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

int main() {
    int n,value;
    scanf("%d", &n);
    
    stack<pair<int, int>> s;
    long long sum=0;
    long long tmpSum;
    long long tmpX;
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &value);
        tmpX = i;
        
        while (!s.empty() && s.top().second >= value){
            tmpSum = (i - s.top().first) * s.top().second;
            sum = sum < tmpSum ? tmpSum : sum;
            tmpX = s.top().first;
            s.pop();
        }
        
        s.push(make_pair(tmpX, value));
    }
    
    while (! s.empty()){
        tmpSum = (n+1 - s.top().first) * s.top().second;
        sum = sum < tmpSum ? tmpSum : sum;
        s.pop();
    }
    printf("%lld\n", sum);
}

#include<iostream>
using namespace std;

/*
 st is stack
 sp is stack point
 */
int st[100001];
int sp;

int a[100001];
int n;

int main(){
    cin.tie(0);
    ios::sync_with_stdio();
    
    scanf("%d", &n);
    for(int i = 1; i <=n ;i++)
        scanf("%d", a+i);
    
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int left, right;
        while(sp > 0 && a[st[sp-1]] >= a[i]){
            int height = a[st[sp-1]];
            sp--; // pop()과 같은 역할이다.
            
            if(sp == 0)
                left = 1;
            else
                left = st[sp-1] + 1;
            
            right = i-1;
            int width = ( right-left+1 ) * height;
            if(ans < width)
                ans = width;
        }
        st[sp] = i;
        sp++; // push()와 같은 역할이다.
    }
    
    while(sp > 0){
        int left, right;
        int height = a[st[sp-1]];
        sp--;
        
        if(sp == 0) left = 1;
        else left = st[sp-1] + 1;
        
        
        right = n;
        int width = ( right-left+1 ) * height;
        if(ans < width)
            ans = width;
    }
    
    printf("%d\n", ans);
    return 0;
}

#include <iostream>
using namespace std;
long long hist[100000];

int stack[10001];
int top = -1;

void push(int x){
    stack[++top] = x;
}

int empty() {
    if( top < 0 )
        return 1;
    else
        return 0;
}

void pop() {
    if (empty() == 1){ }
    else {
        stack[top--] = 0;
    }
}

void size(){
    cout << top + 1 << "\n";
}


int main(){
    int n;
    
    long long max = -1;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++){
        scanf("%lld", &hist[i]);
        while (!empty() && hist[stack[top]] > hist[i]){
            int j = stack[top];
            pop();
            long long width = i;
            
            if (!empty())
                width -= stack[top] + 1; // width = width - ( stack[top] + 1 ) 이다.
            long long cmp = hist[j] * width;
            max = max < cmp ? cmp : max;
        }
        push(i);
    }
    
    while (!empty()) {
        int j = stack[top];
        pop();
        long long width = n;
        if (!empty())
            width -= stack[top] + 1;
        long long cmp = hist[j] * width;
        max = max < cmp ? cmp : max;
    }
    
    printf("%llu\n", max);
    
    return 0;
}

#include <cstdio>
#include <stack>
using namespace std;
int a[100000];
int main() {
    int n;
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    stack<int> s;
    int ans = 0;
    for (int i=0; i<n; i++) {
        int left = i;
        while(!s.empty() && a[s.top()] > a[i]) {
            int height = a[s.top()];
            s.pop();
            int width = i;
            if (!s.empty()) {
                width = (i - s.top() - 1);
            }
            if (ans < width*height) {
                ans = width*height;
            }
        }
        s.push(i);
    }
    while(!s.empty()) {
        int height = a[s.top()];
        s.pop();
        int width = n;
        if (!s.empty()) {
            width = n-s.top()-1;
        }
        if (ans < width*height) {
            ans = width*height;
        }
    }
    printf("%d\n",ans);
    return 0;
}