42. Trapping Rain Water

seanlook 發布于2019-08-14 16:31 / 2101人閱讀

摘要：題目解答左邊比右邊小或者大都可以盛水，所以我們不能直接確定右邊是否會有一個柱子比較大，能盛所有現在積攢的水。那么我們就找到中間最大的那個柱子，把它分成左右兩邊，那么不管從左邊還是右邊都能保證最后可以有最高的柱子在，之前盛的水都是有效的

題目：
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.

解答：

public class Solution {
    public int trap(int[] height) {
        //左邊比右邊小或者大都可以盛水，所以我們不能直接確定右邊是否會有一個柱子比較大，能盛所有現在積攢的水。
        //那么我們就找到中間最大的那個柱子，把它分成左右兩邊，那么不管從左邊還是右邊都能保證最后可以有最高的柱子在，之前盛的水都是有效的
        if (height.length <= 2) return 0;
        int maxHeight = 0, maxIndex = 0;
        int result = 0;
        //find the max height and its index
        for (int i = 0; i < height.length; i++) {
            if (height[i] > maxHeight) {
                maxHeight = height[i];
                maxIndex = i;
            }
        }
        //left part
        int maxLeft = height[0];
        for (int i = 1; i < maxIndex; i++) {
            if (height[i] > maxLeft) {
                maxLeft = height[i];
            } else {
                result += maxLeft - height[i];
            }
        }
        //right part
        int maxRight = height[height.length - 1];
        for (int i = height.length - 2; i > maxIndex; i--) {
            if (height[i] > maxRight) {
                maxRight = height[i];
            } else {
                result += maxRight - height[i];
            }
        }
        return result;
    }
}

GPU云服務器云服務器 Rain Trapping water 42u機柜

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66207.html

Leetcode[42] Trapping Rain Water

摘要：復雜度思路因為蓄水多少取決于比較短的那塊板的長度。代碼復雜度思路考慮說明時候需要計算蓄水量當的時候，需要計算能儲存的水的多少。每次還需要取出一個作為中間值。如果則一直向里面壓進去值，不需要直接計算。 Leetcode[42] Trapping Rain Water Given n non-negative integers representing an elevation map ...

jonh_felix 2019-08-14 15:03 評論0 收藏0
leetcode42 Trapping Rain Water

摘要：我先通過堆棧的方法，找到一個封閉區間，該區間可以盛水，該區間的右節點可以作為下一個封閉區間的起點。思路三堆棧的聰明使用在這里，堆棧允許我們漸進的通過橫向分割而非之前傳統的縱向分割的方式來累加計算盛水量。題目要求 Given n non-negative integers representing an elevation map where the width of each bar...

GitCafe 2019-08-16 10:37 評論0 收藏0
LeetCode.42 接雨水(Trapping Rain Water)(JS)

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

MartinDai 2019-08-23 18:05 評論0 收藏0
[Leetcode] Trapping Rain Water 積水問題

摘要：從右向左遍歷時，記錄下上次右邊的峰值，如果左邊一直沒有比這個峰值高的，就加上這些差值。難點在于，當兩個指針遍歷到相鄰的峰時，我們要選取較小的那個峰值來計算差值。所以，我們在遍歷左指針或者右指針之前，要先判斷左右兩個峰值的大小。 Trapping Rain Water Given n non-negative integers representing an elevation map ...

caohaoyu 2019-08-14 12:29 評論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 2019-08-16 10:28 評論0 收藏0