题目

题目解读

1.木桶效应，短边决定蓄水量
2.选定 i < j，水量 = (j - i) × min(height[i], height[j])

开始解题

一、暴力枚举

        思路：

                双重循环尝试所有组合 (i, j)，计算面积并更新最大值。

        核心流程：

                1.初始化 maxArea = 0。

                2.外层循环 i 从 0 到 n-2。

                3.内层循环 j 从 i+1 到 n-1：

                        计算 area = (j - i) * min(height[i], height[j])。

                        maxArea = max(maxArea, area)。

                4.返回 maxArea。

        代码

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

 二、双指针法

        思路：       

                想要一次遍历找到最大水量，我们需要一种聪明的方式排除不可能成为答案的柱子组合。

                初始时，左右指针放在数组两端（此时宽度最大）。对于当前的两根柱子，容器的水量取决于较矮的那根（短板效应）。
                如果我们固定短板，向内移动另一根更高的柱子，宽度减小，但高度最大也只能是短板的高度，因此面积不可能增大。
                因此，唯一可能得到更大面积的方法，就是向内移动短板，虽然宽度变小，但有可能遇到更高的短板，从而抬高水位。

                所以策略是：每次计算当前面积后，移动高度较小的那个指针。当两个指针相遇时，所有可能的最优解都已被检视过。

        核心流程：

                1.初始化 left = 0, right = n - 1, maxArea = 0。
                2.当 left < right 时循环：
                        计算当前面积 area = (right - left) * min(height[left], height[right])。
                        更新 maxArea = max(maxArea, area)。
                        若 height[left] < height[right]，则 left++；否则 right--。
                3.返回 maxArea。

        代码

public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;
        while (left < right) {
            int minH = Math.min(height[left], height[right]);
            int area = (right - left) * minH;
            maxArea = Math.max(maxArea, area);
            // 移动较短的那边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }

感谢您能够看到这里，一起见证小何同学的算法学习，如果您有不同的见解，希望能得到您的指点和点悟；如果您是和我一样的同学，也希望这篇文章能对您有所帮助。