leetcode42雨水

题目链接：https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked

法一：前缀和
求能装多少水，即左右两边木板高度的最小值减去数组元素。左边木板高度即左区间最大高度，右边木板高度即右区间最大高度。第一个数组存储从最左边到第i个位置的最大高度（前缀最大值），第二个数组存储从最右边到第i的位置的最大高度（后缀最大值）。对于当前位置的前缀最大值 = max(前一个位置的前缀最大值,当前位置的最大高度)。每一个位置的前后缀数组里的值的最小值减去数组中的数值即水

classSolution{intpre_max[20010];intsuf_max[20010];public:inttrap(vector<int>&nums){intn=nums.size();pre_max[0]=nums[0];for(inti=1;i<n;++i)pre_max[i]=max(pre_max[i-1],nums[i]);suf_max[n-1]=nums[n-1];for(inti=n-2;i>=0;--i)suf_max[i]=max(suf_max[i+1],nums[i]);intret=0;for(inti=0;i<n;++i){ret+=min(pre_max[i],suf_max[i])-nums[i];}returnret;}};

法二：优化为双指针（好处，不用创建数组）
前缀最大值 > 后缀最大值，则最大高度为后缀最大值，水量为这个最大高度减去数组元素，右指针左移

classSolution{public:inttrap(vector<int>&nums){intn=nums.size();intpre_max=0,suf_max=0;intleft=0,right=n-1;intret=0;while(left<=right){pre_max=max(pre_max,nums[left]);suf_max=max(suf_max,nums[right]);if(pre_max<suf_max){ret+=pre_max-nums[left++];}elseret+=suf_max-nums[right--];}returnret;}};