目錄
之前看面試題的時(shí)候，看到了一個(gè)接雨水的問(wèn)題悠砚，和小黃鴨討論之后，覺(jué)得很有趣呢堂飞，這里和大家分享一下這個(gè)解法灌旧。后來(lái)看到LeetCode上面有這道題，題號(hào)42绰筛，有興趣的可以做一下枢泰。
問(wèn)題描述
給定n個(gè)非負(fù)整數(shù)表示每個(gè)寬度為1的柱子的高度圖，計(jì)算彼此排列的柱子铝噩，下雨之后能接多少雨水衡蚂。
示例1：
輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
實(shí)例2：
輸入：height = [4,2,0,3,2,5]
輸出：9
你能不能先思考一下，遇到這種問(wèn)題骏庸，你要怎么做呢?
問(wèn)題分析
首先我們可以根據(jù)給的數(shù)組毛甲，先畫出來(lái)柱子的長(zhǎng)度。
那么我們?cè)趺创_定接的雨水的量呢?當(dāng)然是兩個(gè)都高中間低的地方具被，來(lái)存儲(chǔ)水玻募，下面陰影的部分就是儲(chǔ)存水的位置。
那么我們需要對(duì)左邊和右邊最高水位做一個(gè)統(tǒng)計(jì)一姿，這邊使用到了兩個(gè)輔助數(shù)組
一個(gè)用來(lái)儲(chǔ)存左邊的最大接雨水?dāng)?shù)补箍，一個(gè)存儲(chǔ)右邊的最大接雨水?dāng)?shù)。
選擇兩個(gè)中最小的那個(gè)作為存儲(chǔ)水的量
當(dāng)然還要減去自己柱子的高度啸蜜。剩下的坑雅，就是可以接的雨水了。
代碼整理
function trap(height) {
if(!height.length) return 0;
let left = []
let right = []
let lmax = rmax = 0
let len = height.length
let result = 0
// 把左右最大出水量求出來(lái)
for(let i = 0; i < len; i++) {
lmax = Math.max(height[i], lmax)
rmax = Math.max(height[len-i-1], rmax)
left[i] = lmax
right[len- i - 1] = rmax
}
// 算出最小的然后累加
for(let i = 0; i < len; i++) {
result += Math.min(left[i],right[i]) - height[i]
}
return result
};
如果想要寫法上優(yōu)化一下衬横，可以第二次遍歷的時(shí)候可以使用reduce
function trap(height) {
if(!height.length) return 0;
let left = []
let right = []
let lmax = rmax = 0
let len = height.length
for(let i = 0; i < len; i++) {
lmax = Math.max(height[i], lmax)
rmax = Math.max(height[len-i-1], rmax)
left[i] = lmax
right[len- i - 1] = rmax
}
return height.reduce((prev, item, index) => {
return prev + Math.min(left[index],right[index]) - item
}, 0)
};
分析
- 時(shí)間復(fù)雜度O(n)
- 空間復(fù)雜度O(n)
其實(shí)右邊數(shù)組的值的存儲(chǔ)是可以省略的裹粤，雖然都是空間復(fù)雜度O(n)，但是也算小小的優(yōu)化點(diǎn)。
function trap(height) {
if(!height.length) return 0;
let left = []
let lmax = rmax = 0
let len = height.length
let result = 0
for(let i = 0; i < len; i++) {
lmax = Math.max(height[i], lmax)
left[i] = lmax
}
// 從后往前遍歷
for(let i = len - 1; i >= 0; i--) {
rmax = Math.max(height[i], rmax)
result += Math.min(left[i],rmax) - height[i]
}
return result
};
