11.盛最多水的容器

给定 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

思路一：暴力的双重循环

时间复杂度为,在数据量较大的时候，性能很差

思路二：双指针

• 核心思想： 减少循环的核心思路是省去没有必要的遍历，并且确保所需的答案一定能被遍历到。容器的盛水量取决于容器的底和容器较短的那条高。 容器高度较大的一侧的移动只会造成容器盛水量减小，所以应当移动高度较小一侧的指针，并继续遍历，直至两指针相遇 。
• 分析：主要的困惑在于如何移动双指针才能保证最大的盛水量被遍历到假设有左指针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;
}

参考