LeetCode: 42. Trapping Rain Water

题目描述

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

题目大意是: 给定 n 个非负整数，代表地势的高低，宽度都为1，计算给定的地势情况下，能容纳多少积水。比如给定的例子中积水为: 1+4+1 = 6(蓝色部分表示积水)。

解题思路

这道题的思路和 LeetCode: 11. Container With Most Water 类似。 也是用两个指针 (i 和 j) 从左右两边开始搜索，每次计算 i, j 构成的容器的容量， 最后减去被高地势占据的容量即可。

AC 代码

class Solution {
public:
    int trap(vector<int>& height) {
        int i = 0, j = height.size()-1;
        int lastMin = 0;
        int water = 0;
        while(i < j){
            water += (min(height[i], height[j])-lastMin)*(j-i-1);

            if(height[i] < height[j])
            {
                lastMin = height[i], ++i;
                while(i < j && height[i] <= lastMin)
                {
                    water -= height[i];
                    ++i;
                }
                if(i < j) water -= lastMin;
            }
            else
            {
                lastMin = height[j], --j;
                while(i < j && height[j] <= lastMin)
                {
                    water -= height[j];
                    --j;
                }
                if(i < j) water -= lastMin;
            }
        }

        return water;
    }
};