Loading...
首页 计算机 算法 算法题 中等

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

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

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

** 说明：** 你不能倾斜容器。

示例 1：

img

输入：[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 <= 105
  • 0 <= height[i] <= 104

解法一：暴力法（会超时）

思路：循环遍历计算出每种结果值，取最大值。

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                // 最大值（面积）= 最短的一侧 * 下标长度
                max = Math.max(max, Math.min(height[i], height[j]) * (j - i));
            }
        }
        return max;
    }
}
解法二：暴力法（优化版）
思路：逆向遍历 + 剪枝法。
class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = height.length - 1; j > i; j--) {
                // 第一个条件，以实例 1 举例，当 i=0，height [i]=1，只需要遍历一次 j，后面的 j-- 算出来的值肯定会更小
                // 第二个条件，以实例 1 举例，当 i=1，height [i]=8，j=8，height [j]=7，此时 max=49，max/height [i]=6，也就是后面的下标长度只要小于等于				  // 6，肯定算出来的面积只会更小
                if (height[i] < height.length - j || (max / height[i]) >= (j - i) ) break;
				// 最大值（面积）= 最短的一侧 * 下标长度
                max = Math.max(max, Math.min(height[i], height[j]) * (j - i));
            }
        }
        return max;
    }
}
解法三：双指针
思路：一个指针指向头，一个指针指向尾，最大值为 S (i,j) = min (height [i], height [j]) * (j - i)，根据这个公式可以看出
若移动值小的下标， min (height [i], height [j]) 可能会变大，最终 S 也会变大。
若移动值大的下标， min (height [i], height [j]) 可能会不变或者更小，最终 S 可能会变小。
class Solution {
    public int maxArea(int[] height) {
        int max = 0, i = 0, j = height.length - 1;
        while (i < j){
            // 只移动值小的下标
            max = height[i] < height[j] ?
                    Math.max(max, (j - i) * height[i++]) :
                    Math.max(max, (j - i) * height[j--]);
        }
        return max;
    }
}
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/container-with-most-water