问题描述 链接到标题

11.盛最多水的容器

解题思路 链接到标题

本题暴力解法，时间复杂度为$O(n^2)$(会超时，没试过)，为了降低时间复杂度，考虑使用双指针。

那么，本题需要考虑的就是左指针l和右指针r如何向中间靠拢：

  • if (height[l] >= height[r])，说明容器容积是由height[r]来决定的，这时候，l向中间考虑，只可能会缩小容积，因此应该r--;
  • if (height[l] < height[r])，说明容器容积由height[l]来决定，这时候，r向中间靠拢，只会缩小容积，因此应该l++;

代码 链接到标题 

#include <vector>
using std::vector;
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int res = 0;
        while (l < r) {
            if (height[l] >= height[r]) {
                res = max(res, (r - l) * height[r]);
                r--; // 因为此时，增加l只可能缩小res，所以减少r
            } else {
                res = max(res, (r - l) * height[l]);
                l++; // height[l] < height[r], 此时减少r也只会缩小res，所以增加l
            }
        }
        return res;
    }
};