這篇“C++收集雨水問題怎么解決”文章的知識(shí)點(diǎn)大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價(jià)值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“C++收集雨水問題怎么解決”文章吧。

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、微信小程序、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了承德縣免費(fèi)建站歡迎大家使用！

收集雨水

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.

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. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

這道收集雨水的題跟之前的那道 Largest Rectangle in Histogram 有些類似，但是又不太一樣，先來看一種方法，這種方法是基于動(dòng)態(tài)規(guī)劃 Dynamic Programming 的，維護(hù)一個(gè)一維的 dp 數(shù)組，這個(gè) DP 算法需要遍歷兩遍數(shù)組，第一遍在 dp[i] 中存入i位置左邊的最大值，然后開始第二遍遍歷數(shù)組，第二次遍歷時(shí)找右邊最大值，然后和左邊最大值比較取其中的較小值，然后跟當(dāng)前值 A[i] 相比，如果大于當(dāng)前值，則將差值存入結(jié)果，參見代碼如下：

C++ 解法一：

class Solution {
public:
    int trap(vector& height) {
        int res = 0, mx = 0, n = height.size();
        vector dp(n, 0);
        for (int i = 0; i < n; ++i) {
            dp[i] = mx;
            mx = max(mx, height[i]);
        }
        mx = 0;
        for (int i = n - 1; i >= 0; --i) {
            dp[i] = min(dp[i], mx);
            mx = max(mx, height[i]);
            if (dp[i] > height[i]) res += dp[i] - height[i];
        }
        return res;
    }
};

Java 解法一：

public class Solution {
    public int trap(int[] height) {
        int res = 0, mx = 0, n = height.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; ++i) {
            dp[i] = mx;
            mx = Math.max(mx, height[i]);
        }
        mx = 0;
        for (int i = n - 1; i >= 0; --i) {
            dp[i] = Math.min(dp[i], mx);
            mx = Math.max(mx, height[i]);
            if (dp[i] - height[i] > 0) res += dp[i] - height[i];
        }
        return res;
    }
}

再看一種只需要遍歷一次即可的解法，這個(gè)算法需要 left 和 right 兩個(gè)指針分別指向數(shù)組的首尾位置，從兩邊向中間掃描，在當(dāng)前兩指針確定的范圍內(nèi)，先比較兩頭找出較小值，如果較小值是 left 指向的值，則從左向右掃描，如果較小值是 right 指向的值，則從右向左掃描，若遇到的值比當(dāng)較小值小，則將差值存入結(jié)果，如遇到的值大，則重新確定新的窗口范圍，以此類推直至 left 和 right 指針重合，參見代碼如下：

C++ 解法二：

class Solution {
public:
    int trap(vector& height) {
        int res = 0, l = 0, r = height.size() - 1;
        while (l < r) {
            int mn = min(height[l], height[r]);
            if (mn == height[l]) {
                ++l;
                while (l < r && height[l] < mn) {
                    res += mn - height[l++];
                }
            } else {
                --r;
                while (l < r && height[r] < mn) {
                    res += mn - height[r--];
                }
            }
        }
        return res;
    }
};

Java 解法二：

public class Solution {
    public int trap(int[] height) {
        int res = 0, l = 0, r = height.length - 1;
        while (l < r) {
            int mn = Math.min(height[l], height[r]);
            if (height[l] == mn) {
                ++l;
                while (l < r && height[l] < mn) {
                    res += mn - height[l++];
                }
            } else {
                --r;
                while (l < r && height[r] < mn) {
                    res += mn - height[r--];
                }
            }
        }
        return res;
    }
}

我們可以對(duì)上面的解法進(jìn)行進(jìn)一步優(yōu)化，使其更加簡潔：

C++ 解法三：

class Solution {
public:
    int trap(vector& height) {
        int l = 0, r = height.size() - 1, level = 0, res = 0;
        while (l < r) {
            int lower = height[(height[l] < height[r]) ? l++ : r--];
            level = max(level, lower);
            res += level - lower;
        }
        return res;
    }
};

Java 解法三：

public class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1, level = 0, res = 0;
        while (l < r) {
            int lower = height[(height[l] < height[r]) ? l++ : r--];
            level = Math.max(level, lower);
            res += level - lower;
        }
        return res;
    }
}

其實(shí)用 stack 的方法博主感覺更容易理解，思路是，遍歷高度，如果此時(shí)棧為空，或者當(dāng)前高度小于等于棧頂高度，則把當(dāng)前高度的坐標(biāo)壓入棧，注意這里不直接把高度壓入棧，而是把坐標(biāo)壓入棧，這樣方便在后來算水平距離。當(dāng)遇到比棧頂高度大的時(shí)候，就說明有可能會(huì)有坑存在，可以裝雨水。此時(shí)棧里至少有一個(gè)高度，如果只有一個(gè)的話，那么不能形成坑，直接跳過，如果多余一個(gè)的話，那么此時(shí)把棧頂元素取出來當(dāng)作坑，新的棧頂元素就是左邊界，當(dāng)前高度是右邊界，只要取二者較小的，減去坑的高度，長度就是右邊界坐標(biāo)減去左邊界坐標(biāo)再減1，二者相乘就是盛水量啦，參見代碼如下：

C++ 解法四：

class Solution {
public:
    int trap(vector& height) {
        stack st;
        int i = 0, res = 0, n = height.size();
        while (i < n) {
            if (st.empty() || height[i] <= height[st.top()]) {
                st.push(i++);
            } else {
                int t = st.top(); st.pop();
                if (st.empty()) continue;
                res += (min(height[i], height[st.top()]) - height[t]) * (i - st.top() - 1);
            }
        }
        return res;
    }
};

Java 解法四：

class Solution {
    public int trap(int[] height) {
        Stack s = new Stack();
        int i = 0, n = height.length, res = 0;
        while (i < n) {
            if (s.isEmpty() || height[i] <= height[s.peek()]) {
                s.push(i++);
            } else {
                int t = s.pop();
                if (s.isEmpty()) continue;
                res += (Math.min(height[i], height[s.peek()]) - height[t]) * (i - s.peek() - 1);
            }
        }
        return res;
    }
}

以上就是關(guān)于“C++收集雨水問題怎么解決”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對(duì)大家有幫助，若想了解更多相關(guān)的知識(shí)內(nèi)容，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。