P1010 67的心下起了大雨

一.解题思路

1.碎碎念

最近一直单曲循环 喜欢-阿肆https://y.qq.com/n/yqq/song/0015EQT708bZlQ.html

好好听呜呜呜听😭了

既然这么好听那就来编一下这个题解吧！

对了！看完题解别直接走哇点个赞求求你了！！！

呜呜呜写题解的时候码蹄杯出结果了，呜呜呜四银一铜，恭喜他们几个进决赛（咬牙切齿版

金银进决赛主包铜奖继🏀杯后再一次失之交臂啊啊啊啊（这件事告诉我们打比赛一定要看排行榜，不然真的会丢大分！！！

2.题目分析

通读完题目，发现这是一道接雨水的题目，我们只需要理解这道题定义的凹陷即可，由题目可知，只要这一块形成一个坑（水深大于0），就是一处凹陷

例如 1 ** 1 这中间的**就是凹陷

​ 0101110

注意：即使中间有凸起，只要凸起的高度低于两侧的最高点（即该处也有积水），水面就会漫过凸起，整个区域仍算作同一个凹陷

而凹陷就以为着可以积水，不过题目并非要求有几格水深，所以只需要做简单的含水判断就好啦

因此，我们只需要找到积水大于0的连续段，就是一处凹陷

理论存在，实践开始！

3.算法实现

1.先预处理左侧及右侧最大值

**L[i]=max(L[i−1],h[i−1])，其中 L[0]=0

R[i]=max(R[i+1],h[i+1])，其中 R[n−1]=0

注意：此处最大值并不包含i这一点

2.计算每个位置的积水量

water[i]=max(0,min(L[i],R[i])−h[i])

3.通过flag标记是否第一次进入该积水区域

4.复杂度

1.时间：O(n)

2.空间：O(n)

二.完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;

    vector<int> h(n);
    for(int i = 0;i<n;++i){
        cin>>h[i];
    }
    
    int ans = 0;
    vector<int> l_max(n,0);
    vector<int> r_max(n,0);

    for(int i = 1;i<n;++i){
        l_max[i] = max(l_max[i-1],h[i-1]);
    }
    for(int i = n-2;i>=0;--i){
        r_max[i] = max(r_max[i+1],h[i+1]);
    }

    bool flag = 0;
    for(int i = 0;i<n;++i){
        int area = max(0LL,min(l_max[i],r_max[i])-h[i]);
        if(area > 0){
            if(!flag){
                ans++;
                flag = 1; 
            }
        }else{
            flag = 0;
        }
    }
    cout<<ans<<'\n';
    return 0;
}

PS：非专业题解！有任何错误记得联系我！！！