题目描述
给定 $n$ 个非负整数表示每个柱子的高度，每个柱子的宽度为 1，计算按此排列的柱子，下雨之后能接多少雨水。
输入格式

  • 第一行包含一个整数 $n$，表示柱子的数量。
  • 接下来的 $n$ 行（或一行内），每行一个非负整数，表示每个位置柱子的高度 $height[i]$。
    输出格式
  • 输出一个整数，表示能够接住的雨水总量。

10
对于每一个单位的我们只需要找到它左边的最大值和右边的最大值,取二者的最小值,再减去这个单位的柱子长度。
用前缀最大值数组存储左边最大值,后缀最大值数组存储右边最大值

#include<iostream>
using namespace std;
int main(){
    int n,sum=0;
    cin>>n;
    int arr[n+1];
    for(int i=1;i<=n;i++)
    cin>>arr[i];
    int left_max[n+1];
    int right_max[n+1];
    for(int i=1;i<=n;i++)
    {
        if(i==1)
        left_max[i]=arr[i];
        else{
            left_max[i]=max(arr[i],left_max[i-1]);
        }
    }
     for(int i=n;i>=1;i--)
    {
        if(i==n)
        right_max[i]=arr[i];
        else{
            right_max[i]=max(arr[i],right_max[i+1]);
        }
    }
    for(int i=2;i<n;i++)
    {
        if(min(right_max[i],left_max[i])<=arr[i])
        sum+=0;
        else
        sum+=min(right_max[i],left_max[i])-arr[i];
    }
    cout<<sum;
}

11
先找到最高的柱子,对它左边的每个柱子,用它左侧的最大高度减去自身高度,对它右边的每个柱子,
用它右侧的最大高度减去自身高度。

#include<iostream>
using namespace std;
int main(){
     int n,sum=0,index=1;
    cin>>n;
    int arr[n+1];
    for(int i=1;i<=n;i++)
    cin>>arr[i];
    int maxhigh=arr[1];
    for(int i=2;i<=n;i++)
        if(arr[i]>maxhigh)
        {
            maxhigh=arr[i];
            index=i;
        }
    
    int maxleft=arr[1];
    for(int i=2;i<index;i++)
    {
        if(arr[i]>maxleft)
        maxleft=arr[i];
        sum+=maxleft-arr[i];
        
    }
    int maxright=arr[n]; 
    for(int i=n-1;i>index;i--) 
    {
        if(arr[i]>maxright)
        maxright=arr[i];
        sum+=maxright-arr[i];
    }
    cout<<sum;

}