[導(dǎo)讀]今天給大家?guī)?lái)的是一道特別特別特別經(jīng)典的題目接雨水問題，這個(gè)問題是很多算法書上面舉例過的題目。雖然是難度題，但是相對(duì)來(lái)說(shuō)還是比較容易理解的，代碼長(zhǎng)度也適中，說(shuō)了這么多，就一個(gè)意思，大家記得打卡這個(gè)題目啊，真的是很nice的一道題，下面我們來(lái)看一下題目描述。
接雨水
示例 1：
輸入：height =?[0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
示例 2：
輸入：height =?[4,2,0,3,2,5]
輸出：9
示例3：
輸入：[4,3,2,0,1,1,5]
輸出：13
說(shuō)明：上面是由數(shù)組 [4,3,2,0,1,1,5]表示的高度圖，在這種情況下，可以接 13個(gè)單位的雨水（見下圖）。
題目解析：
題目代碼：
class?Solution?{
????public?int?
trap(int[]?height)?{
?????????Stack?stack?=?new?Stack();
?????????int?water?=?0;
?????????//特殊情況???????
?????????
if(height.length?< 3){
????
return?0;
?????????}???????
?????????
for(int?i?=?0;?i??????????????
while(!stack.isEmpty()?&&?height[i]?>?height[stack.peek()])???????
?????????????????//棧頂元素
?????????????????int?popnum?=?stack.pop();?
?????????????????//相同元素的情況例1，1?????
?????????????????
while(!stack.isEmpty()&&height[popnum]?==?height[stack.peek()]){
?????????????????????stack.pop();
?????????????????}?
?????????????????//計(jì)算該層的水的單位
?????????????????
if(!stack.isEmpty()){
?????????????????????int?temp?=?height[stack.peek()];//棧頂元素值????????
?????????????????????//高??????
?????????????????????int?hig?=?Math.min(temp-height[popnum],height[i]-height[popnum]);
?????????????????????//寬
?????????????????????int?wid?=?i-stack.peek()-1;
?????????????????????water?+= hig?*?wid;
?????????????????}
?????????????}???????
?????????????//這里入棧的是索引
?????????????stack.push(i);
?????????}
?????????
return?water;
????}
}
這個(gè)題解的圖片太多了，整了挺久，因?yàn)榕吕速M(fèi)了這道經(jīng)典題，所以畫了很多圖片進(jìn)行說(shuō)明，希望可以幫到大家。下周就是字符串啦，大家加油啊！
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
