跳转至

11. 盛最多水的容器#

问题描述#

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 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

示例 3：


输入：height = [4,3,2,1,4]
输出：16

示例 4：


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

 

提示：

  • n = height.length
  • 2 <= n <= 3 * 104
  • 0 <= height[i] <= 3 * 104

解题思路#

方法一：暴力（超时）#

显然问题的答案是得到一组下标值 \((i,j),j\ge i\)，我们首先最容易想到的就是穷举所有的 \((i,j)\) 对，然后迅速写出下面的代码：

1
2
3
4
5
6
7
8
class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        ans = 0
        for i in range(n):
            for j in range(i + 1, n):
                ans = max(ans, (j - i) * min(height[j], height[i]))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                ans = max(ans, (j - i) * min(height[j], height[i]));
            }
        }
        return ans;
    }
};

意料之中，我们的代码通过了所有的示例，但是看到 \(2 \le n \le 3 \times 10^4\)，想着 \(\mathcal{O}(n^2)\) 的复杂度可能在超时边缘，然后。。。。。。

11-1-0

11-1-1

方法二：优化的暴力（超时）#

经过分析发现，如果 \(j\) 从大到小遍历，那么当 \(\texttt{height}[j]\ge\texttt{height}[i]\) 的时候就可以停止了，\(j\) 再小，结果也不会大于 \(\texttt{height}[i]\times(j-i)\) 了。

所以我们又迅速将代码改了一下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)

        ans = 0
        for i in range(n):
            for j in range(n - 1, i, -1):
                ans = max(ans, (j - i) * min(height[j], height[i]))
                if height[j] >= height[i]: break
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = n - 1; j > i; --j) {
                ans = max(ans, (j - i) * min(height[j], height[i]));
                if (height[j] >= height[i]) break;
            }
        }
        return ans;
    }
};

但是算法在最差的情况下（数据降序排列），复杂度还是 \(\mathcal{O}(n^2)\)。

11-2-0

11-2-1

然后卡在了同样的测例，发现除了第一个数，剩下的数果然是降序排列的。这时候一个取巧的方式是，将 \(\texttt{height}\) 翻转后进行计算。

所以该题使用 \(\mathcal{O}(n^2)\) 的复杂度的方法应该过不了（但是可以计算一下顺序对和逆序对的数目，然后再决定是否翻转数组，这样也可以过），AC 至少需要 \(\mathcal{O}(n\log n)\) 的算法。

方法三：排序（通过）#

通过上面的分析，如果需要 \(\mathcal{O}(n\log n)\) 的算法，可能想到就是排序或者二分，这里我们考虑使用排序。

  1. 首先将 \(\texttt{height}\) 升序排列
  2. 从右往左遍历，并记录最大的下标和最小的下标值
  3. 到当前位置时，用当前的高度乘以最大位置差，然后更新最大与最小下标
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def maxArea(self, height: List[int]) -> int:
        p = [[x, i] for i, x in enumerate(height)]
        p.sort()

        ans = 0
        max_i = min_i = p[-1][1]

        for h, i in reversed(p):
            ans = max(ans, h * max(abs(i - max_i), abs(i - min_i)))
            max_i = max(max_i, i)
            min_i = min(min_i, i)

        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        vector<pair<int, int>> p(n);

        for (int i = 0; i < n; ++i) {
            p[i] = {height[i], i};
        }

        sort(p.begin(), p.end());

        int ans = 0, max_i = p[n - 1].second, min_i = p[n - 1].second;

        for (int i = n - 2; i >= 0; --i) {
            ans = max(ans, p[i].first * max(abs(p[i].second - min_i), abs(p[i].second - max_i)));
            max_i = max(max_i, p[i].second);
            min_i = min(min_i, p[i].second);
        }

        return ans;
    }
};

方法四：双指针（通过）#

按照方法二的思路，当 \(i=0\) 时，用 \(j\) 表示 \(j\) 从右往左遍历到的第一个 大于 \(\texttt{height}[i]\) 的位置，显然对于 \(j\) 之后的每个数来说，\(\texttt{height}[0]\) 就是他们取得最大值的位置，所以我们遍历完这些数后，可以删掉这些数。

对于 \(j\)，我们可以将 \(i\) 从左往右遍历到第一个大于 \(\texttt{height}[j]\) 的位置，然后删去该位置之前的数，重复上述步骤直到 \(i = j\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans = 0
        L, R = 0, len(height) - 1

        while L < R:
            while L < R and height[R] <= height[L]:
                ans = max(ans, (R - L) * height[R])
                R -= 1

            while L < R and height[L] <= height[R]:
                ans = max(ans, (R - L) * height[L])
                L += 1

        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int ans = 0;
        int L = 0, R = n - 1;

        while (L < R) {
            while (L < R && height[R] <= height[L]) {
                ans = max(ans, (R - L) * height[R]);
                --R;
            }
            while (L < R && height[L] <= height[R]) {
                ans = max(ans, (R - L) * height[L]);
                ++L;
            }
        }

        return ans;
    }
};
返回顶部

在手机上阅读