Container With Most Water 383
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.
Notice
You may not slant the container.
Example
Given [1,3,2], the max area of the container is 2.
Solution
这题和Trapping rain water不一样,取任意两个木板后,中间的木板可以忽略。
首先想到的是两次循环找最大值,时间复杂度O(n^2)。
如果用前后指针则可以将时间复杂度降到O(n)。计算取前后指针为木板时的面积,然后移动较短的那一个。保留最大面积。
代码如下:
O(n^2)
public class Solution {
/**
* @param heights: an array of integers
* @return: an integer
*/
public int maxArea(int[] heights) {
// write your code here
if(heights == null || heights.length <= 1){
return 0;
}
int area = 0;
for(int i = 0; i < heights.length - 1; i++){
for(int j = i + 1; j < heights.length; j++){
int width = j - i;
int height = Math.min(heights[i], heights[j]);
area = Math.max(area, width * height);
}
}
return area;
}
}
O(n)
public class Solution {
/**
* @param heights: an array of integers
* @return: an integer
*/
public int maxArea(int[] heights) {
// write your code here
if(heights == null || heights.length <= 1){
return 0;
}
int start = 0;
int end = heights.length - 1;
int sum = 0;
while(start < end){
sum = Math.max(sum, (end - start) * Math.min(heights[start], heights[end]));
if(heights[start] < heights[end]){
start++;
}else{
end--;
}
}
return sum;
}
}