11. 盛最多水的容器(中等)

1，问题描述

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

2，思考过程

​ 暴力破解就是遍历2次完成，时间复杂度为O(n^2)

​ 双指针的方法就是左右两端进行相向遍历，时间复杂度为O(n)

3，代码处理

public class _11盛最多水的容器 {

    // 双指针的方法可以解决，本质就是2次遍历(超时！==要求时间复杂度较低)
    public int maxArea_n2(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;
    }

    // 两边向中间移动，时间复杂度O(n)
    // 优先变动（舍弃）高度低的墙！
    // 官方题解是这个解题方式
    public int maxArea(int[] height) {
        int max = 0;
        int left = 0;
        int right = height.length - 1;
        while (left < right){
            max = Math.max(max, Math.min(height[left], height[right]) * (right - left));
            if(height[left] < height[right]){
                left++;
            }else{
                right--;
            }
        }
        return max;
    }
}

4，思考过程

​ 贪心算法是一种在每一步选择中都采取当前状态下的最优决策的算法。

​ 在特定问题中，它通过局部最优选择来期望达到全局最优解。

​ 在本题中，使用贪心算法通过不断比较左右指针所指线段的高度，优先舍弃高度低的墙，从而在每次决策中尽可能地使容器容纳更多的水，最终找到最大水量。这种算法的优点是时间复杂度相对较低，能够高效地解决问题。