题目描述

给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明:你不能倾斜容器。
示例 1:
图片说明
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2:
输入:height = [1,1]
输出:1

示例 3:
输入:height = [4,3,2,1,4]
输出:16

示例 4:
输入:height = [1,2,1]
输出:2

提示:
n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104

题解

双For循环+优化

class Solution {
    public int maxArea(int[] height) {
        // 数组+指针模拟栈
        int[]stack=new int[height.length];
        int top=0;
        int max=0;
        // 假设height[i]>=height[i+1],则相同右边界的情况下,以i作为左边界的容器的容积较大。
        for(int i=0;i<height.length;++i){
            // 可能的左边界
            if(top==0||height[i]>height[stack[top-1]]){
                stack[top++]=i;
            }else{
                // 作为右边界
                for(int j=0;j<top;++j){
                    int capacity=Math.min(height[stack[j]],height[i])*(i-stack[j]);
                    if(capacity>max){
                        max=capacity;
                    }
                    if(height[stack[j]]>=height[i]){
                        break;
                    }
                }
            }
        }

        // 栈内递增的最大值作为容器右边界
        int right=stack[top-1];
        for(int i=0;i<top-1;++i){
            int capacity=height[stack[i]]*(right-stack[i]);
            if(capacity>max){
                max=capacity;
            }
        }
        return max;
    }
}

双指针

  • 左右指针分别作为容器的左右边界,假设height[left]<=height[right],则容器的容积=height[left]*(right-left)。
  • 假设移动右指针,则新容器的容积=min(height[right-1],height[left])*(right-1-left)。
    • 假设height[left]<=height[right-1],则容器的容积=height[left]*(right-1-left)<height[left]*(right-left)。
    • 假设height[left]>height[right-1],则容器的容积=height[right-1]*(right-1-left)<height[left]*(right-left)。

可见,在height[left]<=height[right]情况下,移动右指针,得到的容器的容积肯定是减小的。因此,只能移动左指针,即:移动较小的指针。

class Solution {
    public int maxArea(int[] height) {
        // 左右指针分别作为容器的左右边界
        int left=0;
        int right=height.length-1;
        int max=0;
        while(left<right){
            int capacity=Math.min(height[left],height[right])*(right-left);
            if(capacity>max){
                max=capacity;
            }
            // 移动较小的指针你
            if(height[left]<height[right]){
                ++left;
            }else{
                --right;
            }
        }
        return max;
    }
}