資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目解答左邊比右邊小或者大都可以盛水，所以我們不能直接確定右邊是否會(huì)有一個(gè)柱子比較大，能盛所有現(xiàn)在積攢的水。那么我們就找到中間最大的那個(gè)柱子，把它分成左右兩邊，那么不管從左邊還是右邊都能保證最后可以有最高的柱子在，之前盛的水都是有效的
題目：
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.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
解答：
public class Solution {
public int trap(int[] height) {
//左邊比右邊小或者大都可以盛水，所以我們不能直接確定右邊是否會(huì)有一個(gè)柱子比較大，能盛所有現(xiàn)在積攢的水。
//那么我們就找到中間最大的那個(gè)柱子，把它分成左右兩邊，那么不管從左邊還是右邊都能保證最后可以有最高的柱子在，之前盛的水都是有效的
if (height.length <= 2) return 0;
int maxHeight = 0, maxIndex = 0;
int result = 0;
//find the max height and its index
for (int i = 0; i < height.length; i++) {
if (height[i] > maxHeight) {
maxHeight = height[i];
maxIndex = i;
}
}
//left part
int maxLeft = height[0];
for (int i = 1; i < maxIndex; i++) {
if (height[i] > maxLeft) {
maxLeft = height[i];
} else {
result += maxLeft - height[i];
}
}
//right part
int maxRight = height[height.length - 1];
for (int i = height.length - 2; i > maxIndex; i--) {
if (height[i] > maxRight) {
maxRight = height[i];
} else {
result += maxRight - height[i];
}
}
return result;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66207.html
摘要：復(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...
摘要：一題目接雨水給定個(gè)非負(fù)整數(shù)表示每個(gè)寬度為的柱子的高度圖，計(jì)算按此排列的柱子，下雨之后能接多少雨水。上面是由數(shù)組表示的高度圖，在這種情況下，可以接個(gè)單位的雨水藍(lán)色部分表示雨水。提交，答案錯(cuò)誤。出錯(cuò)的測(cè)試用例為。 做有意思的題是要付出代價(jià)的，代價(jià)就是死活做不出來(lái)。 一、題目 接雨水： 給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖，計(jì)算按此排列的柱子，下雨之后能接多少雨水。show...
摘要：從右向左遍歷時(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 ...
407. Trapping Rain Water II 題目鏈接：https://leetcode.com/problems... 參考discussion里的解法：https://discuss.leetcode.com/... 參考博客里的解釋?zhuān)篽ttp://www.cnblogs.com/grandy... public class Solution { public int tra...
閱讀 667·2019-08-30 15:44
閱讀 1387·2019-08-30 11:02
閱讀 2996·2019-08-29 18:42
閱讀 3517·2019-08-29 16:16
閱讀 1725·2019-08-26 13:55
閱讀 1778·2019-08-26 13:45
閱讀 2393·2019-08-26 11:43
閱讀 3257·2019-08-26 10:32
