企业建立网站账户如何做,网站建设类书籍,株洲网站建设服务,单页产品销售网站如何做推广这道题呢可以按列来累加#xff0c;就是先算第1列的水的高度然后再加上第2列水的高度……一直加到最后就是能加的水的高度#xff0c;我想到了这里然后就想第i列的水其实就是第i-1列和i1列中最小的高度减去第i列的高度#xff0c;但是其实并不是#xff0c;比如示例中的第5… 这道题呢可以按列来累加就是先算第1列的水的高度然后再加上第2列水的高度……一直加到最后就是能加的水的高度我想到了这里然后就想第i列的水其实就是第i-1列和i1列中最小的高度减去第i列的高度但是其实并不是比如示例中的第5列他的告诉是0左右两边是1但水是2然后看题解了。
第i列的水其实与第i-1列和i1列的水并没有关系而是和第i列左边所有柱子中最高的和第i列右边所有柱子中最高的有关
当第i列左右两边的最高柱子中较矮的比第i列要高那么第i列能装的水就是较矮的高度-第i列的高度。如果左右两边最高的柱子都比第i列的柱子矮的话那么第i列能装的水就是0。所以算出每一列能装的水然后全部加起来就是能接到的雨水以下的代码
class Solution {public int trap(int[] height) {int n height.length;int ans 0;for(int i 1;in-1;i){int leftMaxHeight 0;for(int j i-1;j0;j--){if(height[j] leftMaxHeight)leftMaxHeightheight[j];}int rightMaxHeight 0;for(int k i1;kn;k){if(height[k] rightMaxHeight)rightMaxHeightheight[k];}int min Math.min(rightMaxHeight, leftMaxHeight);ans min height[i] ? min-height[i] : 0;}return ans;}
}
这个算法每次都要找出某一列左边的最高的柱子和右边的最高柱子就多了一层循环算法还可以优化创建一个left_max数组和right_max数组left_max[i]表示第i列左边的最高的柱子right_max[i]同理。用动态规划的方法来填充这两个数组。
left_max[i] Math,max(left_max[i-1] ,height[i-1]);就是说第i列左边最高的柱子是第i-1列左边的最高柱子第i-1列的高度的最大值,right_max[i]同理。以下是代码
public int trap(int[] height) {int sum 0;int[] max_left new int[height.length];int[] max_right new int[height.length];for (int i 1; i height.length - 1; i) {max_left[i] Math.max(max_left[i - 1], height[i - 1]);}for (int i height.length - 2; i 0; i--) {max_right[i] Math.max(max_right[i 1], height[i 1]);}for (int i 1; i height.length - 1; i) {int min Math.min(max_left[i], max_right[i]);if (min height[i]) {sum sum (min - height[i]);}}return sum;
}
