LeetCode 每日一題 11. 盛最多水的容器 詳細題解 多種解法

LeetCode 每日一題 11. 盛最多水的容器

  大家好，我叫亓官劼（qí guān jié ）

題目

難度 中等

給你 n 個非負整數 a1，a2，…，an，每個數代表坐标中的一個點 (i, ai) 。在坐标内畫 n條垂直線，垂直線 i 的兩個端點分别為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。

**說明：**你不能傾斜容器，且 n 的值至少為 2。

圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。

示例：

輸入：[1,8,6,2,5,4,8,3,7]
輸出：49      

題解一：暴力解法

  這題讓我們求兩個柱線間能存放的最大空間是多少，第一種解法當然就是暴力啦！我們周遊這個​

​height​

​數組，對每一個位置對我們計算從目前位置到後面的每個柱子間所能存水的數量，如果找出每個位置的最大值，如果比目前的最大值大，則更新，否則不更新。

完整的代碼為：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0;
        int length = height.size();
        for(int i = 0; i < length; i++){
            int now = 0;
            for(int j = length-1; j >= i; j--){
                int temp = min(height[i],height[j]) * (j - i);
                now = temp > now ? temp : now;
            }
            ans = now > ans ? now : ans;
        }
        return ans;       
    }
};      

送出這段代碼的時候，我們發現在樣例49/50的時候逾時了，說明這次的資料量比較大，暴力竟然沒法AC了！那我們就進一步的優化我們的算法吧！

題解二：雙指針

  這題的最優解應該就是雙指針了，我們分别從兩端開始移動，記錄目前能夠存水的值，并且更新​

​ans​

​，然後開始移動位置，我們移動高度較小的一段。即如果左面的高度小，則左面的位置右移；如果右面的高度小，則右面的位置左移。這樣來更新我們的ans的值，最終取的最大值。

完整的題解代碼為：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int ans = 0;
        while (l < r) {
            int area = min(height[l], height[r]) * (r - l);
            ans = max(ans, area);
            if (height[l] <= height[r]) {
                ++l;
            }
            else {
                --r;
            }
        }
        return ans;
    }
};