---

前言

每天一道算法题，今天我们来做盛最多水的容器！

---

题目链接：11.盛最多水的容器

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

示例 1：

输入： [1,8,6,2,5,4,8,3,7]
输出： 49
解释： 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入： height = [1,1]
输出： 1

提示：

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

算法分析

题目解析

题目中说给定一个长度为 n 的整数数组。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。其中(i, 0) 和 (i, height[i]) 结合图片可以看出指的就是第 i 条垂线的长度。现在题目要求我们找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。题目的意思很好理解，但问题是要怎么用代码的方式写出来？

解法

在看完这个题目的时候，不出意外我最先想到的解法就是直接暴力枚举所有的情况，两层 for 循环就行了。

class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int ret = -1;
        for (int i = 0; i < height.size() - 1; i++)
        {
            for (int j = 1 + i; j < height.size(); ++j)
            {
                int h = height[i] < height[j] ? height[i] : height[j];
                int tmp = (j - i) * (h);
                if (tmp > ret)
                ret = tmp;
                //ret = ret > (j - i) * (height[i]) ? ret : (j - i) * (height[i]);
            }
        }
        return ret;
    }
};

两层 for 循环嵌套，时间复杂度为 O(n^2)，很显然结果超时了。

所以在后来看了别人的分析之后突然就明白了，这里主要是要通过研究在数组中找最大容积的过程，搞懂一个规律，有了这个规律之后这道题的解法也就出来了。

我们先在示例1中随便挑几个数看一下

假设我们要在这几个数里面找可以容纳最多水的容器，我们先看最两边的线，它俩组成的容积是12。下面重点来了，如果我们下面直接从最右边开始往左遍历数组，这就成了暴力枚举了。

但如果我们从6开始往4位置缩（->），可以看出，容积的长度是不断减小的。而高度有两种情况，第一种是有些数的高度比6大，这个时候容积的高度还是4；第二种是有些数的高度比6小，这个时候容积的高度就变成了小的那个数了，但不论是哪种情况，我们可以看到容积的大小总是在不断变小的，即4和数组中别的数结合的容积必然要比最左边的6小，所以我们可以大胆的把4这个元素给干掉，这就减少了我们遍历数组的时间。

这个时候我们就好奇了，如果不是从6开始往4位置缩（->），而是从4开始往6位置缩（<-），结果会有什么不同吗？我们可以来分析一下，首先可以确定容积的长度一定实在减小的，但是高度也有两种情况，第一种是有些数高度比4小，这个时候容积的高度就是小的那个数，第二种是有些数高度比4大，那这个时候容积的高度就变成了大的那个数了，所以容积大大小到底是变大还是变小是不确定的。

回顾一下我们刚才分析的过程，我们是从数组的两边开始，计算出一个容积之后就把两边数当中小的那个给干掉，不断重复这个过程知道两个数相遇，且这里我们只遍历数组一遍，所以时间复杂度为 O(n)。

综上，我们可以用双指针来解这道题！

代码实现

class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int ret = -1;
        int i = 0;
        int j = height.size() - 1;
        while(i < j)
        {
            int w = j - i;
            int h = height[i] < height[j] ? height[i++] : height[j--];
            int tmp = w * h;
            if (tmp > ret)
            ret = tmp;
        }
        return ret;
    }
};

虽然都是用的双指针，但每个人实际写的代码都会有所不同，上面的代码仅供大家参考。

---

完！