题解 | #容器盛水问题#

特别需要注意数据的输入输出的范围，确定合适的数据类型，不然会溢出
注意sum+=width*height; 以及sum需要定义为long型

#include<stack>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int nums[n];
    for(int i=0;i<n;i++){
        scanf("%d", &nums[i]);
    }
    long sum=0;
    //单调递减序列
    stack<int>stk;
    
     for(int i=0;i<n;i++){
         while(!stk.empty() && nums[i]>nums[stk.top()]){
             int cur=stk.top();
             stk.pop();
//              if(stk.size()) sum += 1l*(i-stk.top()-1)*(min(nums[stk.top()],nums[i])-nums[cur]);
             if(stk.empty()){
                 continue; //左边没有比当前柱子高的，盛不了水
             }
             int left=stk.top();
             int right=i;
             long width=right-left-1;
             long height=min(nums[left], nums[right])-nums[cur];
             sum+=width*height;
         }
         stk.push(i);
     }
     //剩下的找不到右边更高的柱子，所以也积不了水，不用出栈了
    printf("%ld\n", sum);
    return 0;
}