题解 | #容器盛水问题#

//本题的暴力解为对于每一个位置都求出左边的最大值和右边的最大值然后求出当前位置的盛水量
//这种方法简单但时间复杂度高O（N²）
//还可以进行预处理时间复杂度可以降至O（N）但是时间复杂度为O（N）
//这两种方法较为简单这里用最优解可以做到时间复杂度为O（N）空间复杂度为O（1）
#include<bits/stdc++.h>
using namespace std;
long long min(long long a,long long b){
    return a>b?b:a;
}
long long max(long long a,long long b){
    return a>b?a:b;
}
int main(){
    //申请两个变量leftMax和rightMax代表左右两边已经处理过的区域最大的数
    //初始时leftMax为arr[0],rightMax为arr[n-1]因为最左边和最右边肯定不可能盛水
    //设置两个前后指针i和j表示前面未遍历的第一个数和后面未遍历的第一个数
    //初始时i=1，j=n-2;
    long long n;
    cin>>n;
    long long *arr=new long long[n];
    for(long long i=0;i<n;i++)
        cin>>arr[i];
    if(n==1){//数组中只有一个数时不可能盛水
        cout<<0<<endl;
        return 0;
    }
    long long leftMax=arr[0],rightMax=arr[n-1];
    long long L=1,R=n-2;//左右开始遍历的位置
    long long res=0;//最终的结果值
    //本来while里面写的是并行的if语句结果不行
    //后来改成if else 就过了，想了半天不知道哪的问题
    //得出一个结论并行if语句很危险
    //知道的大佬评论告诉我
    while(L<=R){
        if(arr[L]>=leftMax){//当前值比它左边的最大值还要大，此时不可能有积水，更新leftMax的值
            leftMax=arr[L];
            L++;//向右移动
        }
       else if(arr[R]>=rightMax){//同理
            rightMax=arr[R];
            R--;
        }
       else if(leftMax<=rightMax){//此时L位置的盛水量可以求出来了
            res+=max(min(leftMax,rightMax)-arr[L],0);
            L++;
        }
        else {//此时R位置的盛水量可以求出来了
            res+=max(min(leftMax,rightMax)-arr[R],0);
            R--;
        }
    }
    cout<<res<<endl;
    return 0;
}