LeetCode 11. 盛最多水的容器

迫于最近比较无聊，重操Leetcode旧业，顺带写一下题解。

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例：

 

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

解法一

首先最简单的思路是直接暴力枚举，依次取两条线计算其储水量，取其中的最大值作为结果。代码如下：

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

很显然上述代码的时间复杂度为O(n^2)，超出时间限制，需要进行优化。

解法二

我们仔细观察题目的示例，每个容器的容量应该是min(左侧高度, 右侧高度)*二者之间的距离，那么在上面进行暴力枚举的时候，有些计算是不必要的。例如，当选定左侧高度为1时，那么无论右侧高度为多少，最后容器的有效高度都只有1，那么只有当右侧高度为7时容器的容量才会最大，因为此时容器的长度最长。因此我们可以有如下代码：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        for (int i = 0; i < height.size() - 1; i++) {
            for (int j = height.size() - 1; j > i; j--) {
                int cur = min(height[i], height[j]) * (j - i);
                if (cur > res) 
                    res = cur;
                if (height[i] < height[j])
                    break;
            }
        }
        return res;
    }
};

这样最坏情况下，时间复杂度依然为O(n^2)，最坏情况为线的高度倒序排列，对每个i，都需要依次遍历一遍j。运行发现可以通过，但是运行时间为1148ms，仅超过5.60%，仍有优化空间。

解法三

当height[i] < height[j]时，i直接+1，因为无论后续j如何变化，总的高度不会超过height[i] res = min(height[i], height[j]) * (j - i + 1).当height[i] < height[j]时，随着j减小，在i保持不变时，res' < height[i] * (j - i + 1)，因此可以省略掉对j的后续遍历，直接i + 1，重新开始计算。而当height[i] > height[j]时，同样的道理，在j保持不变时，随着i增大，res' < height[j] * (j - i + 1)，因此可以省略掉对i的后续遍历，直接j - 1，重新开始计算。而我们的上述代码的问题在于，对于每个新的i，都从height的末尾重新遍历j，导致多了很多不必要的计算。将两部分结合起来，得到：

1. 当height[i] > height[j]时，j--；
2. 当height[i] < height[j]时，i++。
3. 当height[i] = height[j]时，如果在i和j之间不存在更大的height，那么i++或者j–对容量无影响。如果在i和j之间存在更大的height，那么会存在两种情况：
   1. 存在i < m < j，m唯一，且height[m] > height[i] = height[j]，此时最大容量仍由i, j 决定，与m无关，因此i + 1或j - 1对结果无影响。
   2. 存在i < m < n < j, 且height[m] > height[n] > height[i] = height[j]，此时最大容量取决于height[n] * (m - n + 1)与height[i] *(i - j + 1)的大小，同样i + 1或j - 1对结果无影响。
   3. 存在i < m < n < j, 且height[n] > height[m] > height[i] = height[j]，此时与上述2.相同. 综上，得到最终优化后的代码如下：

      class Solution
      {
      public:
       int maxArea(vector<int> &height)
       {
       int i = 0;
       int res = 0;
      
       for (int i = 0, j = height.size() - 1; i < j; )
       {
           int cur = min(height[i], height[j]) * (j - i);
           if (cur > res)
               res = cur;
           if (height[i] <= height[j])
               i++;
           else 
               j--;
       }
       return res;
       }
      };
      

每个height仅遍历一次，时间复杂度为O(n)。运行时间68ms，击败82.8%。