11. 盛最多水的容器

暴力解法（超时）

import java.util.Arrays;

class Solution {
    public int maxArea(int[] height) {

        /**
         * 暴力解法，直接使用额外数组存放每一个坐标为左边界时的最大面积，最后对数组求最大值
         */
        int[] res = new int[height.length];

        for (int i = 0; i < height.length; i++) {

            int max = 0;

            for (int j = i + 1; j < height.length; j++) {

                int area = Math.min(height[i], height[j]) * (j - i);

                if (area > max){
                    max = area;
                }
            }

            res[i] = max;
        }

        return Arrays.stream(res).max().getAsInt();
    }
}

/**
 * 时间复杂度 O(n^2)
 * 空间复杂度 O(n)
 */

优化1——双指针法

class Solution {
    public int maxArea(int[] height) {

        /**
         * 双指针法遍历
         * 如果往左或者往右的面积都小于当前的面积，则先记录下当前面积，其不一定是最大面积
         * 然后让边界值小的那个边界移动
         */
        int left = 0;
        int right = height.length - 1;
        int area = 0;
        int max = 0;

        while (left < right){

            area = Math.min(height[left], height[right]) * (right - left);

            if (Math.min(height[left + 1], height[right]) * (right - left - 1) > area){
                left++;
            }
            else if (Math.min(height[left], height[right - 1]) * (right - left - 1) > area){
                right--;
            }
            else {

                if (area > max) {
                    max = area;
                }

                if (height[left] <= height[right]){
                    left++;
                }
                else {
                    right--;
                }
            }
        }

        return max;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

优化2——简化边界移动的判断条件

class Solution {
    public int maxArea(int[] height) {

        /**
         * 双指针法遍历
         * 每次让边界值小的那个边界移动，实时更新当前最大的面积
         */
        int left = 0;
        int right = height.length - 1;
        int area = 0;
        int max = 0;

        while (left < right){

            area = Math.min(height[left], height[right]) * (right - left);
            max = Math.max(area, max);

            if (height[left] < height[right]){
                left++;
            }
            else {
                right--;
            }
        }

        return max;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

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