題目描述

給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。 感謝 Marcos 貢獻此圖。

示例:

輸入: [0,1,0,2,1,0,1,3,2,1,2,1] 輸出: 6

1、 暴力法

/***接雨水，暴力解法* 對于數組中的每個元素，我們找出下雨后水能達到的最高位置，等于兩邊最大高度的較小值減去當前高度的值。* @param height* @return*/ public int trap(int[] height) {if(height == null || height.length < 2) {return 0;}int leftMax=0, rightMax=0;int count=0;for(int i=1;i<height.length-1;i++) {leftMax=0;rightMax=0;for(int j=0;j<i;j++) {leftMax = Math.max(leftMax, height[j]);}for(int j=height.length-1; j>i;j--) {rightMax = Math.max(rightMax, height[j]);}if(leftMax>0 && rightMax>0 && Math.min(leftMax, rightMax)>height[i]) {count+=(Math.min(leftMax, rightMax) - height[i]);}}return count;}

2、空間換時間

/***接雨水* 用空間換時間，記錄下每個節點的左側最大值，右側最大值* 對于數組中的每個元素，我們找出下雨后水能達到的最高位置，等于兩邊最大高度的較小值減去當前高度的值。* @param height* @return*/ public int trap(int[] height) {if(height == null || height.length < 2) {return 0;}int[] leftMax = new int[height.length];for(int i=1;i<height.length;i++) {leftMax[i] = Math.max(leftMax[i-1], height[i-1]);}int[] rightMax = new int[height.length];for(int i=height.length-2;i>=0;i--) {rightMax[i] = Math.max(rightMax[i+1], height[i+1]);}int count=0;for(int i=1;i<height.length-1;i++) {if(Math.min(leftMax[i], rightMax[i])>height[i]) {count+=(Math.min(leftMax[i], rightMax[i])-height[i]);}}return count;} 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的接雨水的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。