Leetcode(11) - 盛水最多的容器- java版

Leetcode(11) - 盛水最多的容器- java版

题目

难度: 中等

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明: 你不能倾斜容器，且 n 的值至少为 2。

img

示例1:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

一. 暴力法

具体思路:

考虑每对可能出现的线段组合,并找出这些情况之下的最大面积

实现:

class Solution {
    public int maxArea(int[] height) {
        int ret = 0;
     for(int i =0; i<height.length;i++){
            for(int j =i+1;j<height.length;j++){    
                ret = Math.max(ret,Math.min(height[i],height[j]) * (j-i));
            }         
        } '
        return ret;
    }
}

二. 双指针法

具体思路:
由于面积取决于边长较短的那一端,所以如果想要获得更大的面积,边长较短的一端必须舍弃,去追求更大的高度来弥补宽度的减少.而如果舍弃的是长度较长的一端,那么因为高度受限于长度较短的一端,所以面积不会增大.

我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 max 来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 max，并将指向较短线段的指针向较长线段那端移动一步。

实现:

class Solution {
    public int maxArea(int[] height) {
         int max = 0,left = 0,right = height.length-1;
        while(left < right){
            max = Math.max(max,Math.min(height[left],height[right])* (right-left) );
            if(height[left] < height[right])
                left++;
            else right--;
        }
        return max;
    }
}

参考文章

• LeetCode官方题解