亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專(zhuān)欄INFORMATION COLUMN

Leetcode[42] Trapping Rain Water

jonh_felix / 1426人閱讀

摘要：復(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 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.
Two Pointer

復(fù)雜度
O(N), O(1);

思路
因?yàn)樾钏嗌偃Q于比較短的那塊板的長(zhǎng)度。所以每次當(dāng)左指針指向的板比較短的時(shí)候，就將其設(shè)置為一個(gè)bound,每次向右移動(dòng)，觀察是否有比左邊這個(gè)bound小的板子的存在，如果有，說(shuō)明到這個(gè)位置可以蓄水。

代碼

public int trap(int[] height) {
    int res = 0;
    int left = 0, right = height.length - 1;
    while(left < right) {
        if(height[left] < height[right]) {
            int bound = height[left];
            int i = left + 1;
            while(i < right && height[i] < bound) {
                res += bound - height[i];
                i ++;
            }
            left = i;
        }
        else {
            int bound = height[right];
            int i = right - 1;
            while(i > left && height[i] < bound) {
                res += bound - height[i];
                i --;
            }
            right - i;
        }
    }
    return res;
}
Stack

復(fù)雜度
O(N), O(N)

思路
考慮說(shuō)明時(shí)候需要計(jì)算蓄水量：
當(dāng)val > stack.peek()的時(shí)候，需要計(jì)算能儲(chǔ)存的水的多少。每次還需要取出一個(gè)mid作為中間值。
如果val < stack.peek(),則一直向stack里面壓進(jìn)去值，不需要直接計(jì)算。

代碼

public int trap(int[] height) {
    int res = 0;
    Stack stack = new Stack<>();
    for(int i = 0; i < height.length; i ++) {
        if(!stack.isEmpty() && height[i] > height[stack.peek()]) {
            while(!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int mid = stack.pop();
                if(!stack.isEmpty()) {
                    res += (Math.min(height[stack.peek()], height[i]) - height[mid]) * (i - stack.peek() - 1);
                }
            }
        }
        stack.push(i);
    }
    return res;
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/65261.html

相關(guān)文章

  • leetcode42 Trapping Rain Water

    摘要：我先通過(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...

    GitCafe 評(píng)論0 收藏0

  • LeetCode.42 接雨水(Trapping Rain Water)(JS)

    摘要：一題目接雨水給定個(gè)非負(fù)整數(shù)表示每個(gè)寬度為的柱子的高度圖，計(jì)算按此排列的柱子，下雨之后能接多少雨水。上面是由數(shù)組表示的高度圖，在這種情況下，可以接個(gè)單位的雨水藍(lán)色部分表示雨水。提交，答案錯(cuò)誤。出錯(cuò)的測(cè)試用例為。 做有意思的題是要付出代價(jià)的，代價(jià)就是死活做不出來(lái)。 一、題目 接雨水： 給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖，計(jì)算按此排列的柱子，下雨之后能接多少雨水。show...

    MartinDai 評(píng)論0 收藏0

  • [Leetcode] Trapping Rain Water 積水問(wèn)題

    摘要：從右向左遍歷時(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 ...

    caohaoyu 評(píng)論0 收藏0

  • 407. Trapping Rain Water II

    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...

    wenzi 評(píng)論0 收藏0

  • [LintCode/LeetCode] Trapping Rain Water [棧和雙指針]

    摘要：一種是利用去找同一層的兩個(gè)邊，不斷累加寄存。雙指針?lè)ǖ乃枷胂日业阶笥覂蛇叺牡谝粋€(gè)峰值作為參照位，然后分別向后向前每一步增加該位與參照位在這一位的差值，加入，直到下一個(gè)峰值，再更新為新的參照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...

    bluesky 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<