LeetCode011- Container With Most

Container With Most Water

Question:

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note:

You may not slant the container and n is at least 2.

Container With Most Water

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example1:

Input: [1,8,6,2,5,4,8,3,7]

Output: 49

解法代码

import static java.lang.System.out;

public class LeetCode011 {

    public static void main(String[] args) {
        int[] height = new int[]{1,8,6,2,5,4,8,3,7};
        out.println(new LeetCode011().maxArea(height));
        height = new int[]{1,100,98,2,5,4,8,3,7};
        out.println(new LeetCode011().maxArea(height));
        height = new int[]{1,2};
        out.println(new LeetCode011().maxArea(height));
    }
    
    public int maxArea(int[] height){
        int maxArea = 0;
        int i = 0;
        int j = height.length - 1;
        while(i < j) {
            int tempArea = Math.min(height[i], height[j])*(j-i);
            if(tempArea > maxArea) {
                maxArea = tempArea;
            }
            if(height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return maxArea;
    }
}

Output：

49
98
1

Time And Space Complexity

Time: 只需要遍历一次
Space: 不需要使用额外的存储空间

Tips

• 可以使用简单的暴力破解法，时间复杂度为，效率比较低。
• 另外一种就是双指针法，这种方法背后的思路在于，两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。
  我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量maxArea来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新maxArea，并将指向较短线段的指针向较长线段那端移动一步。
  这种计算方式就是不断缩短x坐标的长度，并且计算每个x坐标长度所能获取到的最大面积，并更新maxArea的值，每一次的移动都是保留能计算出较大面积的垂直高度。
  具体处理过程可以参考如下图片。
• 以下图片来源于LeetCode
  
  
  
  
  
  
  
  

暴力解法

//两次循环，暴力求解代码
//时间复杂度：$O(n^2)$，空间复杂度$O(1)$
public int maxArea(int[] height){
    int maxArea = 0;
    for(int i = 0; i < height.length - 1; i++) {
        for(int j = i +1; j < height.length; j ++) {
            int tempArea = Math.min(height[i], height[j])*(j-i);
            if(tempArea > maxArea) {
                maxArea = tempArea;
            }
        }
    }
    return maxArea;
}

代码优化

    /** 
      * 对代码进行简单的优化，更简洁清晰
      */
    public int maxArea(int[] height){
        int maxArea = 0;
        int i = 0;
        int j = height.length - 1;
        while(i < j) {
            //计算求面积的x坐标值
            int xAxis = j - i;
            //计算求面积的y坐标值，计算完后y坐标较小的向中心移一个位置
            int lengthMin = (height[i] < height[j]) ? height[i++] : height[j--];
            maxArea = Math.max(lengthMin*xAxis, maxArea);
        }
        return maxArea;
    }