首页 > 代码库 > leetcode第一刷_Trapping Rain Water
leetcode第一刷_Trapping Rain Water
很有意思的题目,我一开始的思路受计算柱状型最大面积那道题的影响,想每次求两种满足特定关系的柱子之间的水的量,结果各种错,各种特殊情况需要排除,我意识到是自己的思路有问题了。
停下来想一下水的体积到底跟什么有关系?当然可以把是水的地方都加起来,这样必须看两个柱子之间的高低关系,还要考虑底部的高度。还有一种方法呢,求整个区域的面积,然后把不是水的地方去掉,剩下的就是水的体积。这种方法好在那里呢?这种方法所需要的信息都很容易获得,总的面积怎么求呢?一左一右两个指针,然后维护一个当前最底部的高度,如果这两个指针中最小的那个都比最底部的高度高,那么整个图形的总的面积应该加上他们之间超出最底部的那部分。升高最底部的那个变量为两个柱子中较矮的那个,下一轮循环,移动较矮的那个柱子,直到两个指针相遇为止。如果出现其中一个或两个指针位于最底部下面怎么办呢,那说明他肯定被淹没到整个图形的面积中了,直接更新指针进行下一轮。至于该去掉的部分,其实就是多有的柱子,这个值在什么时候计算都可以。
class Solution { public: int trap(int A[], int n) { if(n < 2) return 0; int l=0, r=n-1, curlevel=0, all=0, block=0; while(l<=r){ if(min(A[l], A[r])>curlevel){ all += (min(A[l], A[r])-curlevel)*(r-l+1); curlevel = min(A[l], A[r]); } if(A[l]<A[r]) block += A[l++]; else block += A[r--]; } return all-block; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。