每日一题-20240211

发表于 更新于 分类于 阅读次数： 本文字数： 588 阅读时长 ≈ 2 分钟

题目描述

11. 盛最多水的容器

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

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

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

说明：你不能倾斜容器。

示例 1：

img

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

示例 2：

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

提示：

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

解题思路

双重循环

循环计算不同组合容器大小，取最大值返回

双指针

  1. 初始化： 双指针 i , j 分列水槽左右两端；
  2. 循环收窄： 直至双指针相遇时跳出；
    更新面积最大值 res ；
    选定两板高度中的短板，向中间收窄一格；
  3. 返回值： 返回面积最大值 res 即可；

核心思想在于，由于需要移动指针，底边一定变小：

  • 若向内移动短板 ，水槽的短板可能变大，因此下个水槽的面积 可能增大 。
  • 若向内移动长板 ，水槽的短板不变或变小，因此下个水槽的面积 一定变小

代码实现

双重循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution11Case1 {
    /**
     * 此方法超出时间限制
     *
     * @param height
     * @return int
     * @author Forest Dong
     * @date 2024/03/06 17:06
     */
    private static int maxArea(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int water = (j - i) * Math.min(height[i], height[j]);
                if (water > max ) {
                    max = water;
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.err.println(maxArea(height));
    }
}

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution11Case2 {
    /**
     * 双指针
     *
     * @param height
     * @return int
     * @author Forest Dong
     * @date 2024/03/06 17:13
     */
    private static int maxArea(int[] height) {
        int i = 0, j = height.length - 1;
        int max = (height.length - 1) * Math.min(height[i], height[j]);
        for (int k = 0; k < height.length; k++) {
            if (i == j) {
                break;
            }
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
            if ((j - i) * Math.min(height[i], height[j]) > max) {
                max = (j - i) * Math.min(height[i], height[j]);
            }
        }
        return max;
    }

    private static int maxArea1(int[] height) {
        int i = 0, j = height.length - 1;
        int max = 0;
        while (i < j) {
            max = height[i] < height[j] ?
                    Math.max((j - i) * Math.min(height[i++], height[j]), max) :
                    Math.max((j - i) * Math.min(height[i], height[j--]), max);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.err.println(maxArea1(height));
    }
}