11. [M] Container With Most Water

https://leetcode.com/problems/container-with-most-water/

暴力搜索

最简单直接暴力的方案，时间复杂度 O(n^2)，空间复杂度 O(1)。

// 388 ms
class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length - 1; i++) {
            for (int j = 1; j < height.length; j++) {
                int capacity = (j - i) * Math.min(height[i], height[j]);
                max = capacity > max ? capacity : max;
            }
        }
        return max;
    }
}

第一步优化，内部循环 j 无需从 1 开始，可从 i + 1 开始

// 205 ms
class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length - 1; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int capacity = (j - i) * Math.min(height[i], height[j]);
                max = capacity > max ? capacity : max;
            }
        }
        return max;
    }
}

第二步优化，外层循环只需计算比之前高的柱子。由于越往后容器越窄，因此比之前低的柱子围起来的水量一定是更少的。

// 126 ms
class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int lastMaxHeight = 0;
        for (int i = 0; i < height.length - 1; i++) {
            if (height[i] > lastMaxHeight) {
                lastMaxHeight = height[i];
                for (int j = i + 1; j < height.length; j++) {
                    int capacity = (j - i) * Math.min(height[i], height[j]);
                    max = capacity > max ? capacity : max;
                }
            }
        }
        return max;
    }
}

两侧夹逼

从两侧夹逼，每次从高度比较低的一侧向中心移动。时间复杂度 O(n)，空间复杂度 O(1)。

原理是：面积取决取宽度和高度。先取最大宽度，那么当宽度变小的时候，只有尽量取高点，才能保证面积最大。因此每次向中心移动的时候，都保留高点，移动较低点。

// 2ms
class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for (int i = 0, j = height.length - 1; i < j; ) {
            int t = Math.min(height[i], height[j]) * (j-i);
            max = t > max ? t : max;
            t = height[i] > height[j] ? j-- : i++;
        }
        return max;
    }
}