国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

caohaoyu / 2526人閱讀

摘要:從右向左遍歷時(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 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.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

雙指針?lè)?/b> 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

我們使用兩個(gè)指針,一個(gè)從左向右遍歷,一個(gè)從右向左遍歷。從左向右遍歷時(shí),記錄下上次左邊的峰值,如果右邊一直沒(méi)有比這個(gè)峰值高的,就已經(jīng)加上這些差值。從右向左遍歷時(shí),記錄下上次右邊的峰值,如果左邊一直沒(méi)有比這個(gè)峰值高的,就加上這些差值。難點(diǎn)在于,當(dāng)兩個(gè)指針遍歷到相鄰的峰時(shí),我們要選取較小的那個(gè)峰值來(lái)計(jì)算差值。所以,我們?cè)诒闅v左指針或者右指針之前,要先判斷左右兩個(gè)峰值的大小。

注意

移動(dòng)左指針或者右指針時(shí),要先判斷left < right

代碼
public class Solution {
    public int trap(int[] A) {
        if(A.length < 3) return 0;
        int left = 0;
        int right = A.length - 1;
        int sum = 0;
        // 找到左邊的第一個(gè)峰值
        while(left < right && A[left] <= A[left+1]) left++;
        // 找到右邊的第一個(gè)峰值
        while(left < right && A[right] <= A[right-1]) right--;
        while(left < right){
            int leftVal = A[left];
            int rightVal = A[right];
            // 如果左邊峰值較小,先計(jì)算左邊
            if(leftVal < rightVal){
                while(left < right && leftVal >= A[++left]){
                    sum += leftVal - A[left];
                }
            // 如果右邊峰值較小,先計(jì)算右邊
            } else {
                while(left < right && rightVal >= A[--right]){
                    sum += rightVal - A[right];
                }
            }
        }
        return sum;
    }
}

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

轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/64507.html

相關(guān)文章

  • [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
  • 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[42] Trapping Rain Water

    摘要:復(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 ...

    jonh_felix 評(píng)論0 收藏0
  • 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
  • 407. Trapping Rain Water II

    407. Trapping Rain Water II 題目鏈接:https://leetcode.com/problems... 參考discussion里的解法:https://discuss.leetcode.com/... 參考博客里的解釋:http://www.cnblogs.com/grandy... public class Solution { public int tra...

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

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

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<