总结

解决诸如“离我最近且比我大的那个元素？”这样的问题

E - Water Tank

对于每一档板，需要找到在它前面离它最近的档板，在这之间灌满水，再减去已经有水的面积即可

利用单调栈解决

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
void SINGLE_TEST() 
{
    int n;cin>>n;
    vector<int> h(n+1);
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    h[0]=INF;
    ll ans=0;
    vector<int> stk={0};
    for(int i=1;i<=n;i++){
        while(!stk.empty()&&h[stk.back()]<h[i]){
            int t=stk.back();
            stk.pop_back();
            ans-=h[t]*(t-stk.back());
        }
        ans+=h[i]*(i-stk.back());
        cout<<ans+1<<" ";
        stk.push_back(i);
    }
}