Trapping Rain Water--LeetCode

约定不等于承诺〃 2022-08-07 11:47 39阅读 0赞

# 题目： #

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`.

![rainwatertrap.png][]

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.Thanks Marcos for contributing this image!

思路：可以在这个序列中找到最高柱子的位置，那么从两头开始找可以盛水的多少，假如从前开始遍历，需要遍历到柱子最高的位置，遍历到当前位置，如果发现当前的柱子比之前记录的最高的柱子高，那么更新，如果没有之前记录的柱子高，那么就可以计算出当前柱子相对之前的高柱子盛水量。

方法二：也可以借助辅助栈，栈中记录的是位置，栈底始终是遍历到当前位置之前最高的柱子，如果发现当前比栈底柱子的高度还要打，那么需要计算从当前柱子到栈底这段空间可以盛水量，然后将当前为主压入栈，知道最后，栈空间可能不为空，这个时候需要清空栈，需要看当前栈中的柱子可以盛水量。

#include <iostream>
    #include <vector>
    #include <string> 
    using namespace std;
    
    /*
    这个问题可以使用栈来 也可以不用 
    */
    
    int TrapRainWater(vector<int>& vec)
    {
    	int i,maxhigh;
    	maxhigh = 0;
    	int left=0,right = 0;
    	int sum =0;
    	for(i=0;i<vec.size();i++)
    		if(vec[i] > vec[maxhigh])
    			maxhigh = i;
    	
    	for(i=0;i<maxhigh;i++)
    	{
    		if(vec[i] < left)
    			sum +=(left-vec[i]);
    		else
    			left = vec[i];
    	}
    	
    	for(i=vec.size()-1;i>maxhigh;i--)
    	{
    		if(vec[i]<right)
    			sum += (right-vec[i]);
    		else
    			right = vec[i];
    	}
    	return sum;
    }
    int main()
    {
    	int array[]={0,1,0,2,1,0,1,3,2,1,2,1};
    	vector<int> vec(array,array+sizeof(array)/sizeof(int));
    	cout<<TrapRainWater(vec)<<endl;
    }

两次遍历数组，第一次遍历找每个元素右边最大的元素，第二次遍历寻找每个元素左边最大的元素，同时计算该index可以存放的水容积： min\{lefthighest, righthighest\}-A\[i\]

public class Solution {
        public int trap(int[] A) {
            int[] left = new int[A.length];
            int[] right = new int[A.length];
            int sum = 0;
            for (int i=0; i<A.length; i++) {
                if (i == 0) left[i] = 0;
                else {
                    left[i] = Math.max(left[i-1], A[i-1]);
                }
            }
            for (int i=A.length-1; i>=0; i--) {
                if (i == A.length - 1) right[i] = 0;
                else {
                    right[i] = Math.max(right[i+1], A[i+1]);
                }
                if (Math.min(left[i], right[i]) > A[i]) {
                    sum += Math.min(left[i], right[i]) - A[i];
                }
            }
            return sum;
        }
    }

[rainwatertrap.png]: http://www.leetcode.com/wp-content/uploads/2012/08/rainwatertrap.png