資訊專欄INFORMATION COLUMN
摘要：一種是利用去找同一層的兩個(gè)邊，不斷累加寄存。雙指針?lè)ǖ乃枷胂日业阶笥覂蛇叺牡谝粋€(gè)峰值作為參照位，然后分別向后向前每一步增加該位與參照位在這一位的差值，加入，直到下一個(gè)峰值，再更新為新的參照位。
Problem
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.
Note有兩種方法。一種是利用Stack去找同一層的兩個(gè)邊，不斷累加寄存。如[2, 1, 0, 1, 2]，2入棧，1入棧，0入棧，下一個(gè)1大于棧頂元素0，則計(jì)算此處的雨水量加入res，此過(guò)程中0從棧中彈出，1入棧，到下一個(gè)2，先彈出1，由于之前還有一個(gè)1在棧中，所以計(jì)算時(shí)高度的因數(shù)相減為0，雨水量為0，res無(wú)變化，繼續(xù)pop出棧中的元素，也就是之前的1，此時(shí)stack中仍有元素2，說(shuō)明左邊還有邊，繼續(xù)計(jì)算底層高度為1，兩個(gè)值為2的邊之間的水量，加入res。
雙指針?lè)ǖ乃枷耄合日业阶笥覂蛇叺牡谝粋€(gè)峰值作為參照位，然后分別向后（向前）每一步增加該位與參照位在這一位的差值，加入sum，直到下一個(gè)峰值，再更新為新的參照位。這里有一個(gè)需要注意的地方，為什么要先計(jì)算左右兩個(gè)峰值中較小的那個(gè)呢？因?yàn)樵趦蓚€(gè)指針逼近中間組成最后一個(gè)積水區(qū)間時(shí)，要用較短邊計(jì)算。
1. Stack
public class Solution {
public int trapRainWater(int[] A) {
Stack stack = new Stack();
int res = 0;
for (int i = 0; i < A.length; i++) {
if (stack.isEmpty() || A[i] < A[stack.peek()]) stack.push(i);
else {
while (!stack.isEmpty() && A[i] > A[stack.peek()]) {
int pre = stack.pop();
if (!stack.isEmpty()) {
res += (Math.min(A[i], A[stack.peek()]) - A[pre]) * (i - stack.peek() - 1);
}
}
stack.push(i);
}
}
return res;
}
}
2. Two-Pointer
public class Solution {
public int trap(int[] A) {
int left = 0, right = A.length-1, res = 0;
while (left < right && A[left] < A[left+1]) left++;
while (left < right && A[right] < A[right-1]) right--;
while (left < right) {
int leftmost = A[left], rightmost = A[right];
if (leftmost < rightmost) {
while (left < right && A[++left] < leftmost) res += leftmost - A[left];
}
else {
while (left < right && A[--right] < rightmost) res += rightmost - A[right];
}
}
return res;
}
}
雙指針?lè)╱pdate: 2018-3
public class Solution {
public int trap(int[] A) {
if (A == null || A.length < 3) return 0;
//set left/right pointers
int l = 0, r = A.length-1;
//find the first left/right peaks as left/right bounds
while (l < r && A[l] <= A[l+1]) l++;
while (l < r && A[r] <= A[r-1]) r--;
//output
int trappedWater = 0;
//implementation
while (l < r) {
int left = A[l];
int right = A[r];
//when you have a higher RIGHT bound...
if (left <= right) {
//when "l" is highest left bound
//it"s safe to add trapped water RIGHTward
while (l < r && left >= A[l+1]) {
l++;
trappedWater += left - A[l];
}
//when left pointer "l" found "l+1" a higher left bound
//reset the left bound
l++;
}
//when you have a higher LEFT bound...
else {
//when "r" is highest right bound
//it"s safe to add trapped water LEFTward
while (l < r && right >= A[r-1]) {
r--;
trappedWater += right - A[r];
}
//when right pointer "r" found "r-1" a higher right bound
//reset the right bound
r--;
}
}
return trappedWater;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/65612.html
摘要：從右向左遍歷時(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 ...
摘要：我先通過(guò)堆棧的方法，找到一個(gè)封閉區(qū)間，該區(qū)間可以盛水，該區(qū)間的右節(jié)點(diǎn)可以作為下一個(gè)封閉區(qū)間的起點(diǎn)。思路三堆棧的聰明使用在這里，堆棧允許我們漸進(jìn)的通過(guò)橫向分割而非之前傳統(tǒng)的縱向分割的方式來(lái)累加計(jì)算盛水量。 題目要求 Given n non-negative integers representing an elevation map where the width of each bar...
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...
摘要：題目解答左邊比右邊小或者大都可以盛水，所以我們不能直接確定右邊是否會(huì)有一個(gè)柱子比較大，能盛所有現(xiàn)在積攢的水。那么我們就找到中間最大的那個(gè)柱子，把它分成左右兩邊，那么不管從左邊還是右邊都能保證最后可以有最高的柱子在，之前盛的水都是有效的 題目：Given n non-negative integers representing an elevation map where the wid...
閱讀 4524·2021-11-22 13:52
閱讀 2605·2021-11-22 13:52
閱讀 3779·2021-11-19 09:59
閱讀 1313·2021-11-17 09:33
閱讀 2538·2019-08-30 10:53
閱讀 1410·2019-08-29 17:28
閱讀 1382·2019-08-29 17:03
閱讀 3217·2019-08-26 11:31
