資訊專欄INFORMATION COLUMN
摘要：思路對(duì)于每一個(gè)來(lái)說(shuō)，能裝水的容量取決于左右兩側(cè)的最大值。一個(gè)的最終高度容器高度由左右邊界中較小的一個(gè)決定。最終求和得到總蓄水量。對(duì)撞指針問(wèn)題，根據(jù)左右兩邊中較矮的柱子確定當(dāng)前的柱子的最終高度。兩邊最大灌水量分別等于分別當(dāng)前最大高度。
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
思路
對(duì)于每一個(gè)bar來(lái)說(shuō)，能裝水的容量取決于左右兩側(cè)bar的最大值。一個(gè)bar的最終高度 = MIN （Max_left_height, Max_right_height）. 容器高度由左右邊界中較小的一個(gè)決定。
brute force 思路： 掃描兩次，一次從左向右，記錄對(duì)于每一個(gè)bar來(lái)說(shuō)其左側(cè)的bar的最大高度left[i]，一次從右向左，記錄每一個(gè)bar右側(cè)bar的最大高度right[i]。第三次掃描，則對(duì)于每一個(gè)bar，計(jì)算（1）左側(cè)最大height和當(dāng)前bar的height的差值（left[i] - heights[i]） （2）右側(cè)最大height和當(dāng)前bar的height的差值（right[i] - heights[i]），取（1），（2）中結(jié)果小的那個(gè)作為當(dāng)前bar的蓄水量。最終求和得到總蓄水量。
Two Pointers
對(duì)撞指針問(wèn)題， 根據(jù)左右兩邊中較矮的柱子確定當(dāng)前的柱子的最終高度。 兩邊最大灌水量分別等于 分別 += 當(dāng)前最大高度 - heights[i]。
public class Solution {
/**
* @param heights: an array of integers
* @return: a integer
*/
public int trapRainWater(int[] heights) {
// write your code here
if (heights == null || heights.length == 0){
return 0;
}
int left = 0, right = heights.length-1;
if (left >= right){
return 0;
}
//對(duì)撞型指針問(wèn)題， 左右兩邊更低的那根柱子決定了能灌水多少--> 比較左右兩根柱子， 根據(jù)兩者高低靠近， 過(guò)程中更新左邊和右邊的最大值（最大高度）
//兩邊最大灌水量分別 += 當(dāng)前最大高度 - heights[i]
//兩指針未相遇時(shí)， leftH(左邊最大高度) - heights[left]; right
int leftHeight = heights[0];
int rightHeight = heights[heights.length -1];
int res = 0;
while (left < right){
if (heights[left] < heights[right]){
left++;
if (heights[left] < leftHeight){
res += leftHeight - heights[left];
}
else{
leftHeight = heights[left];
}
}else{
right--;
if (heights[right] < rightHeight){
res += rightHeight - heights[right];
}else{
rightHeight = heights[right];
}
}
}
return res;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66475.html
407. Trapping Rain Water II 題目鏈接：https://leetcode.com/problems... 參考discussion里的解法：https://discuss.leetcode.com/... 參考博客里的解釋：http://www.cnblogs.com/grandy... public class Solution { public int tra...
摘要：從右向左遍歷時(shí)，記錄下上次右邊的峰值，如果左邊一直沒(méi)有比這個(gè)峰值高的，就加上這些差值。難點(diǎn)在于，當(dāng)兩個(gè)指針遍歷到相鄰的峰時(shí)，我們要選取較小的那個(gè)峰值來(lái)計(jì)算差值。所以，我們?cè)诒闅v左指針或者右指針之前，要先判斷左右兩個(gè)峰值的大小。 Trapping Rain Water Given n non-negative integers representing an elevation map ...
摘要：復(fù)雜度思路因?yàn)樾钏嗌偃Q于比較短的那塊板的長(zhǎng)度。代碼復(fù)雜度思路考慮說(shuō)明時(shí)候需要計(jì)算蓄水量當(dāng)?shù)臅r(shí)候，需要計(jì)算能儲(chǔ)存的水的多少。每次還需要取出一個(gè)作為中間值。如果則一直向里面壓進(jìn)去值，不需要直接計(jì)算。 Leetcode[42] Trapping Rain Water Given n non-negative integers representing an elevation map ...
摘要：題目解答左邊比右邊小或者大都可以盛水，所以我們不能直接確定右邊是否會(huì)有一個(gè)柱子比較大，能盛所有現(xiàn)在積攢的水。那么我們就找到中間最大的那個(gè)柱子，把它分成左右兩邊，那么不管從左邊還是右邊都能保證最后可以有最高的柱子在，之前盛的水都是有效的 題目：Given n non-negative integers representing an elevation map where the wid...
摘要：一種是利用去找同一層的兩個(gè)邊，不斷累加寄存。雙指針?lè)ǖ乃枷胂日业阶笥覂蛇叺牡谝粋€(gè)峰值作為參照位，然后分別向后向前每一步增加該位與參照位在這一位的差值，加入，直到下一個(gè)峰值，再更新為新的參照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...
閱讀 3029·2023-04-25 18:00
閱讀 2238·2021-11-23 10:07
閱讀 4082·2021-11-22 09:34
閱讀 1257·2021-10-08 10:05
閱讀 1579·2019-08-30 15:55
閱讀 3450·2019-08-30 11:21
閱讀 3352·2019-08-29 13:01
閱讀 1393·2019-08-26 18:26
