[LeetCode Hot 100] LeetCode11. 盛最多的水

题目描述

方法一：暴力，超出时间限制

模拟所有情况，记录最大的体积值。
体积 = Math.min(height[i], height[j]) * (j - i)

class Solution {
    public int maxArea(int[] height) {
        int res = Integer.MIN_VALUE;

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

时间复杂度O(n2)

方法二：双指针

思路：

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

木桶容量由短板决定, 移动长板的话, 水面高度不可能再上升, 而宽度变小了, 所以只有通过移动短板, 才有可能使水位上升.

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1;
        int res = Integer.MIN_VALUE;

        while (i <= j) {
            int area = (j - i) * Math.min(height[i], height[j]);
            if (area > res) {
                res = area;
            }
            if (height[i] <= height[j]) {
                i ++;
            }else if (height[i] > height[j]) {
                j --;
            }
        }
        return res;
    }
}