``` //手搓的分类讨论暴力算法，能过 // #include<bits/stdc++.h> // using namespace std; // int a[30010]; // int n; // vector<pair<int, int>> mh(1, {0, 0});//前下标后值 // long long water =0; // int main(){ // cin>>n; // for(int i = 0; i < n; i++){ // cin>>a[i]; // if(a[i] > mh[0].second){ // mh.clear(); // mh.push_back({i, a[i]}); // } // else if(a[i] == mh[0].second){ // mh.push_back({i, a[i]}); // } // } // //最左边的最长柱左边积水 // int i = 0, j = 0; // while(++i){ // if(a[i] > a[j]){ // int width = i-j-1; // int height = a[j]; // water += width*height; // j++; // while(j < i){ // water -= a[j]; // j++; // } // } // if(a[i] == mh[0].second) break; // } // //最右边的最长柱右边积水 // i = n-1; // j = n-1; // while(--i){ // if(a[i] > a[j]){ // int width = j - i -1; // int height = a[j]; // water += width * height; // j--; // while(j > i){ // water -= a[j]; // j--; // } // } // if(a[i] == mh.back().second) break; // } // //复数最长柱之间的积水 // if(mh.size() > 1){ // for(int i = mh.front().first + 1; i < mh.back().first; i++){ // water += (mh[0].second - a[i]); // } // } // cout<<water<<endl; // } //单调栈正解 #include<bits/stdc++.h> using namespace std; int n; stack<int> s; long long res=0; int main(){ cin>>n; vector<int> v(n); for(int i = 0; i < n; i++){ cin>>v[i]; while(s.size() && v[i] > v[s.top()]){ int right = i; int bottom = s.top(); s.pop(); if(s.size()){ int left = s.top(); res += (min(v[right], v[left])-v[bottom]) * (right - left -1); } } s.push(i); } cout<<res; } ```

dp算法 能接雨水的条件是中间比左右两边都低，所以我们遍历两次，第一次，从左到右遍历一遍，以左边的高度为标准，去接雨水。第二次从右到左遍历一遍，以右边高度为标准去接雨水，由于左右高度是以低的高度作为标准，所以遍历比较每个位置的两次所取的雨水值，取低的加起来即为答案 ``` #include<bits/stdc++.h> using namespace std; # define N 30005 int n,a[N],b[N],dp1[N],dp2[N],sum=0; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; b[i]=a[i]; } for(int i=2;i<n;i++) #从左到右 { if(a[i]>=a[i-1]) { dp1[i]=0; } else if(a[i]<a[i-1]) { dp1[i]=a[i-1]-a[i]; a[i]=a[i-1]; } } for(int i=n-1;i>=2;i--) #从右到左 { if(b[i]>=b[i+1]) { dp2[i]=0; } else if(b[i]<b[i+1]) { dp2[i]=b[i+1]-b[i]; b[i]=b[i+1]; } } for(int i=2;i<n;i++) #取最小 { dp1[i]=min(dp1[i],dp2[i]); } for(int i=1;i<=n;i++) { sum+=dp1[i]; } cout<<sum; return 0; } ```

``` 区左右区间即可 #include<bits/stdc++.h> #define int long long using namespace std; const int N = 5e5 + 9; int a[N]; int l[N]; int r[N]; int ans = 0; signed main(){ ios::sync_with_stdio(0); cin.tie(0); int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int mid = a[1]; for(int i=2;i<=n;i++){ if(mid<a[i]) mid = a[i]; l[i] = mid; } mid = a[n]; for(int i=n-1;i>=1;i--){ if(mid<a[i]) mid = a[i]; r[i] = mid; } for(int i=1;i<=n;i++){ if(a[i]<min(l[i],r[i])) ans+=min(l[i],r[i])-a[i]; } cout<<ans; } ```