首页 > 代码库 > LeetCode: Container With Most Water 解题报告

LeetCode: Container With Most Water 解题报告

Container With Most Water
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.

SOLUTION 1:

采用2个指针一个在左一个在右,计算『桶』可以容纳的水。如果左边低,则左指针右移(试图看可不可以找到更高的bar),反之左移右指针 

 1 public class Solution { 2     public int maxArea(int[] height) { 3         if (height == null) { 4             return 0; 5         } 6          7         int left = 0; 8         int right = height.length - 1; 9         int maxArea = 0;10         11         while (left < right) {12             int h = Math.min(height[left], height[right]);13             int area = h * (right - left);14             maxArea = Math.max(maxArea, area);15             16             if (height[left] < height[right]) {17                 // 如果左边界比较低,尝试向右寻找更高的边界18                 left++;19             } else {20                 // 如果右边界比较低,尝试向左寻找更高的边界21                 right--;22             }23         }24         25         return maxArea;26     }27 }
View Code

代码:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/twoPoints/MaxArea.java

LeetCode: Container With Most Water 解题报告