PIPIOJ 1348: PIPI的序列问题Ⅱ 接雨水 单调栈

题目：

http://39.106.164.46/problem.php?id=1348

思路：

可以先学习一下单调栈：
单调栈

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#include<set>
#define MAX 100005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int n;
int a[MAX];

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    stack<int> s;
    ll ans=0;
    for(int i=0;i<n;i++){
        if(s.empty()||a[s.top()]>=a[i]){
			s.push(i);
		}else{
			while(!s.empty()&&a[s.top()]<a[i]){
				int id=s.top();
                s.pop();
				if(s.empty()) break;
				ll d=i-s.top()-1; //d是宽度
				ll h=min(a[i],a[s.top()])-a[id]; //h是高
				ans+=d*h;
			}
			s.push(i);
		}
    }
    cout<<ans<<endl;
    return 0;
}