给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
思路:
这个题目我记得之前做过来着,好像是双指针
能形成坑的地方就能接雨水,那就是满足高低高这么个形状的
用双指针应该是最合适的方法了
复杂度:
时间复杂度:O(n)
空间复杂度:O(1)
代码:public int trap(int[] height) { int res = 0; int max=0; int maxindex=0; //找到最高的数,和其下标 for(int i=0;i=max){ max = height[i]; maxindex = i; } } //分成最高柱子左边和右边去处理 for(int left =0;left maxindex;--right){ for(int i =right-1;i>=maxindex;--i){ //找到一个比当前列小的 if(height[i]
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)