[leetcode] 42. Trapping Rain Water

[leetcode] 42. Trapping Rain Water

Description

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.

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!

Example:

Input:

[0,1,0,2,1,0,1,3,2,1,2,1]

Output:

6

分析

题目的意思是：给你一个柱形图，然后往里面注水，问柱形图能够装得下多大面积的水。

索引i从左到右，索引j从右往左，遍历的时候寻找左右两边的最大值，如果左边的最大值小于右边的最大值，左边进行操作；如果左边的最大值大于等于右边的最大值，右边进行操作。直到i>j时终止。

代码

class Solution {public: int trap(vector& height) { int i=0; int j=height.size()-1; int sum=0; int left_max=0; int right_max=0; while(i

参考文献

​​42. Trapping Rain Water​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。