单调栈

2019-07-29

题解,

题目地址:https://www.acwing.com/problem/content/133/
这道题目是一道标准的单调栈问题。
由于这道题目求的是直方图中最大的面积。那么我们每次输入一个数就会产生两种情况

  1. 如果输入的这个数比左边那个直方图的高度要大,那么长度就是max{f[i]*(n-i+1)} (1<=i<=n)
  2. 如果输入的这个数比左边那个直方图的高度要大,那么前面的高度就对后面的就没有用了,统计最大值后就讲前面的内容设为这个小的高度
    代码:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    #include<bits/stdc++.h>
    #define N 100010
    using namespace std;
    int n;
    int h[N],w[N];
    stack<long long> s;
    int main() {
    while(true) {
    scanf("%d",&n);
    if(n==0) break;
    for(int i=1;i<=n;i++)
    scanf("%d",&h[i]);
    h[n+1]=0;
    long long ans=0;
    for(int i=1;i<=n+1;i++) {
    if(i==1) {
    s.push(h[i]);
    w[s.size()]=1;
    continue;
    }
    if(h[i]>s.top()) {
    s.push(h[i]);
    w[s.size()]=1;
    }
    else {
    int width=0;
    while(s.size()!=0 && s.top()>h[i]) {
    width+=w[s.size()];
    ans=max(ans,(long long)width*s.top());
    s.pop();
    }
    s.push(h[i]),w[s.size()]=width+1;
    }

    }
    printf("%lld\n",ans);
    }
    return 0;
    }