摘要:從右向左遍歷時(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
摘要:一種是利用去找同一層的兩個(gè)邊,不斷累加寄存。雙指針?lè)ǖ乃枷胂日业阶笥覂蛇叺牡谝粋€(gè)峰值作為參照位,然后分別向后向前每一步增加該位與參照位在這一位的差值,加入,直到下一個(gè)峰值,再更新為新的參照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...
摘要:一題目接雨水給定個(gè)非負(fù)整數(shù)表示每個(gè)寬度為的柱子的高度圖,計(jì)算按此排列的柱子,下雨之后能接多少雨水。上面是由數(shù)組表示的高度圖,在這種情況下,可以接個(gè)單位的雨水藍(lán)色部分表示雨水。提交,答案錯(cuò)誤。出錯(cuò)的測(cè)試用例為。 做有意思的題是要付出代價(jià)的,代價(jià)就是死活做不出來(lái)。 一、題目 接雨水: 給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖,計(jì)算按此排列的柱子,下雨之后能接多少雨水。show...
摘要:復(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 ...
摘要:我先通過(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...
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...
閱讀 3024·2021-10-08 10:18
閱讀 739·2019-08-30 15:54
閱讀 1072·2019-08-29 18:43
閱讀 2447·2019-08-29 15:33
閱讀 1307·2019-08-29 15:29
閱讀 1609·2019-08-29 13:29
閱讀 1030·2019-08-26 13:46
閱讀 1704·2019-08-26 11:55
极致性价比!云服务器续费无忧!
Tesla A100/A800、Tesla V100S等多种GPU云主机特惠2折起,不限台数,续费同价。
NVIDIA RTX 40系,高性价比推理显卡,满足AI应用场景需要。
乌兰察布+上海青浦,满足东推西训AI场景需要