給定 n 個非負(fù)整數(shù) a1，a2，...，an，每個數(shù)代表坐標(biāo)中的一個點 (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。

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

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

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

思路一：暴力的雙重循環(huán)

時間復(fù)雜度為,在數(shù)據(jù)量較大的時候，性能很差

思路二：雙指針

• 核心思想： 減少循環(huán)的核心思路是省去沒有必要的遍歷，并且確保所需的答案一定能被遍歷到。容器的盛水量取決于容器的底和容器較短的那條高。 容器高度較大的一側(cè)的移動只會造成容器盛水量減小，所以應(yīng)當(dāng)移動高度較小一側(cè)的指針，并繼續(xù)遍歷，直至兩指針相遇 。
• 分析：主要的困惑在于如何移動雙指針才能保證最大的盛水量被遍歷到假設(shè)有左指針left和右指針right，且left指向的值小于right的值，假如我們將右指針左移，則右指針左移后的值和左指針指向的值相比有三種情況：
  1. 右指針指向的值大于左指針這種情況下，容器的高取決于左指針，但是底變短了，所以容器盛水量一定變小.
  2. 右指針指向的值等于左指針這種情況下，容器的高取決于左指針，但是底變短了，所以容器盛水量一定變小.
  3. 右指針指向的值小于左指針這種情況下，容器的高取決于右指針，但是右指針小于左指針，且底也變短了，所以容量盛水量一定變小了.
     std:max
     c++ code: AC

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

測試框架：

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

vector<int> stringToIntegerVector(string input) {
    vector<int> output;
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    stringstream ss;
    ss.str(input);
    string item;
    char delim = ',';
    while (getline(ss, item, delim)) {
        output.push_back(stoi(item));
    }
    return output;
}

int main() {
    string line;
    while (getline(cin, line)) {
        vector<int> height = stringToIntegerVector(line);

        int ret = Solution().maxArea(height);

        string out = to_string(ret);
        cout << out << endl;
    }
    return 0;
}

參考