Java每日一题 ~ 盛最多水的容器

. - 力扣（LeetCode）

1.题目解析

 本题的要求就是：给定数组索引之间的差值为宽，元素值中小的为边长求面积。

2.算法分析

思路一：暴力枚举

暴力法的思路是对所有可能的容器组合进行穷举，计算它们能容纳的水量，并找出最大的水量。具体步骤如下：

1. 使用两层嵌套循环遍历所有可能的组合 (i, j)，其中 i 和 j 分别表示容器的两边界的索引。
2. 对于每一对 (i, j)，计算容器的高度为 min(height[i], height[j])，宽度为 j - i，水量即为高度乘以宽度。
3. 维护一个变量 maxArea 来记录找到的最大水量。

暴力法的时间复杂度为 O(n^2)，空间复杂度为 O(1)。

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int n = height.length;
        
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int currentArea = Math.min(height[i], height[j]) * (j - i);
                maxArea = Math.max(maxArea, currentArea);
            }
        }
        
        return maxArea;
    }
}

思路二：双指针（有点小贪心）

对于解法一：枚举了许多没有必要的操作，我们可以按照边最大来找最大的高来找呢？当边确定为左右节点，我们往里面寻找的时候，宽肯定减小，那么我们肯定不能让高也减小吧，高减小会比刚刚的面积大吗？所以我们需要移动短边来使高变大，因为高是又短边决定的，移动高边短边还是一样，找到高的还是高还是不变但宽减小了，找到低的高也减小了。

因此我们的思路就是：贪心让宽最大，然后往里面找，每次都让高有可能变大，然后和面积比较找出最大值，记住移动短边才能让高变大。

双指针法是一种优化的方法，通过从容器的宽度最大开始逐渐减小的方式，来求解问题。具体步骤如下：

1. 使用两个指针 left 和 right 分别指向数组的开头和结尾。
2. 计算当前容器的水量，即 min(height[left], height[right]) * (right - left)，并更新最大水量。
3. 移动高度较小的指针向内移动，因为容器的高度由较小的那个决定，如果移动高度较大的指针，宽度减小，水量只会更少或者不变。

双指针法的时间复杂度为 O(n)，空间复杂度为 O(1)。

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int left = 0, right = height.length - 1;
        
        while (left < right) {
            int currentArea = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, currentArea);
            
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxArea;
    }
}