给定 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;leftmaxindex;--right){
for(int i =right-1;i>=maxindex;--i){
//找到一个比当前列小的
if(height[i]



