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.
大致意思就是給定一組數(shù)匾浪，從中選擇兩個(gè)數(shù)作為高與X軸形成矩形乍丈，求最大的矩形面積
求解思路很簡(jiǎn)單寓娩，矩形的面積由寬度和高度共同決定箕别，其中寬度就是兩個(gè)數(shù)下標(biāo)的距離，而高度主要取決于兩個(gè)數(shù)中的較小者碘梢。初始時(shí)想括，我們?cè)跀?shù)組的起點(diǎn)和終點(diǎn)分別設(shè)置兩個(gè)指針鉴腻，循環(huán)的每一步計(jì)算當(dāng)前矩形的面積并更新最大面積忠寻，然后移動(dòng)較小值的指針縮小矩形寬度進(jìn)入下一循環(huán)惧浴。該算法只需要一層循環(huán)即可計(jì)算出最大的矩形面積，時(shí)間復(fù)雜度O(n)奕剃，空間復(fù)雜度O(1)衷旅，算法的大體過(guò)程如下圖：
代碼如下：
public class Solution {
public int maxArea(int[] height) {
int maxarea = 0, l = 0, r = height.length - 1;
while (l < r)
{
maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
if (height[l] < height[r])
l++;
else
r--;
}
return maxarea;
}
}