LeetCode——盛最多水的容器

题目描述

给你 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;
    }
}