0042._Trapping_Rain_Water.md

42. Trapping Rain Water

难度Hard

刷题内容

原题连接

• https://leetcode.com/problems/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.

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

记录 l = 0，先正向遍历数组，如果 height[i] < height[l],则说明此位置无法积水，记录无法积水的面积，如果 height[i] >= height[l]，则说明[i,l]的区间内可以积水，然后减去无法积水的面积就是积水的面积。遍历完数组之后，如果 l != height.size() - 1，则反向遍历数组，进行上述步骤。

思路 - 时间复杂度: O(N)- 空间复杂度: O(1)******

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0,sum1 = 0,water = 0,i;
        for(i = 1;i < height.size();++i)
            if(height[i] >= height[l])
            {
                water = water + height[l] * (i - l - 1) - sum1;
                l = i;
                sum1 = 0;
            }
            else
                sum1 += height[i];
        if(l !=  (height.size() - 1))
        {
            int temp = l;
            sum1 = 0;
            for(i = height.size() - 2,l = height.size() - 1;i >= temp;--i)
                if(height[i] >= height[l])
                {
                    water = water + height[l] * (l- i - 1) - sum1;
                    l = i;
                    sum1 = 0;
                }
                else
                    sum1 += height[i];
        }
        return water;
    }
};