[導(dǎo)讀]今天給大家?guī)淼氖且坏捞貏e特別特別經(jīng)典的題目接雨水問題，這個問題是很多算法書上面舉例過的題目。雖然是難度題，但是相對來說還是比較容易理解的，代碼長度也適中，說了這么多，就一個意思，大家記得打卡這個題目啊，真的是很nice的一道題，下面我們來看一下題目描述。
接雨水
示例 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
說明：上面是由數(shù)組 [4,3,2,0,1,1,5]表示的高度圖，在這種情況下，可以接 13個單位的雨水（見下圖）。
題目解析：
題目代碼：
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();
?????????????????}?
?????????????????//計算該層的水的單位
?????????????????
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;
????}
}
這個題解的圖片太多了，整了挺久，因為怕浪費了這道經(jīng)典題，所以畫了很多圖片進行說明，希望可以幫到大家。下周就是字符串啦，大家加油?。?/span>
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
