LeetCode 42.Trapping Rain Water (接雨水)

分手后的思念是犯贱 2022-05-11 04:14 259阅读 0赞

题目描述：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

70

示例：

  1. 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
  2. 输出: 6

Accepted C++ Solution:

  1. class Solution {
  2. public:
  3.     int trap(vector<int>& height) {
  4.         int n = height.size();
  5.         int left=0; int right=n-1;
  6.         int res=0;
  7.         int maxleft=0, maxright=0;
  8.         while(left<=right){
  9.             if(height[left]<=height[right]){        //从低的一端注入水
  10.                 if(height[left]>=maxleft) maxleft=height[left];   //当前高度大于最大高度时，装不了水，并更新最大高度
  11.                 else res+=maxleft-height[left];
  12.                 left++;
  13.             }
  14.             else{                                   //从低的一端注入水
  15.                 if(height[right]>=maxright) maxright= height[right]; //同上
  16.                 else res+=maxright-height[right];
  17.                 right--;
  18.             }
  19.         }
  20.         return res;
  21.     }
  22. };

从左到右搜索并分别保持左右最大高度,这就像容器的两边。固定较高的一端，从较低的一端注入水或者更新最大高度。

例如：如果左边的当前高度较低，我们在左边的垃圾箱中填满水。直到在中间汇拢，我们填满了整个容器。

发表评论

表情：
评论列表 （有 0 条评论，259人围观）

还没有评论，来说两句吧...

相关阅读