題目要求
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.
??題目翻譯：給定n個非負整數(shù)澳淑，每一個代表一個坐標點如 ai 代表坐標點 （i, ai）煌寇，對每一個點做垂直于x軸的線段墨林，端點分別是（i, 0）和（i, ai）。現(xiàn)在约巷，找出兩條線段，它們和x軸組成的容器能盛下最多的水。
??簡而言之：根據(jù)木桶效應(yīng)（容量取決于底面積乘以最短板的高度）毅厚，兩條線段較小的一條的高度，乘以它們之間在x軸方向上的距離浦箱，即是容量吸耿。找出最大容量。
題目分析
用兩個for循環(huán)實現(xiàn)的O（n^2）算法超時酷窥⊙拾玻苦想不出優(yōu)化解，參考LeetCode討論區(qū)給出的O（n）算法蓬推，以下是該算法的證明和實現(xiàn)妆棒。
??為了提高效率。我們需要在遍歷的過程中剪去無用的情況同時100%保證最大的值能在我們余下的情況中獲取到沸伏。
??在這個問題中糕珊，我們初始化一左一右兩個游標分別為數(shù)組的端點。每一次向數(shù)組的中間移動值較小的游標一步毅糟，直到兩個游標相遇放接。這個過程中，最大容量100%會被掃描過并獲取,以下是證明：
??1留特、給定a1,a2,a3.....an作為輸入纠脾，假設(shè)a10 和 a20是最大容量的情況。我們需要證明左游標會到達a10蜕青，并且在這期間苟蹈，右游標可以到達a20，因此核心問題變成：當左游標在a10且右游標在a21時右核，下一步的移動是右游標指向a20慧脱。
??2、因為我們總是移動帶有較小值的游標贺喝，如果a10>a21菱鸥，我們會移動把右游標從a21移動到a20。假設(shè)a21>a10躏鱼，則height[a10] x (20-10) < height[a10] x (21-10)氮采，與1中假設(shè)a10和a20是最大容量不符，因此一定有a10>a21染苛。
??3鹊漠、綜上所述：左游標會到達a10，并且在這期間，右游標可以到達a20躯概，由此證明登钥，該算法100%能獲取到最大值。
代碼實現(xiàn)
package com.linsiyue;
public class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
maxArea = Math.max(maxArea,
Math.min(height[left], height[right]) * (right - left));
if (height[left] < height[right])
left++;
else
right--;
}
return maxArea;
}
}
心得總結(jié)
對于最優(yōu)解搜索問題娶靡，直接的思路是分析如何求得最優(yōu)解牧牢，但是有時候思路沒那么好找；我們可以試著通過假設(shè)去固定最優(yōu)解（如本題中假設(shè)a10 和 a20是最大區(qū)域）姿锭，通過分析最優(yōu)解具備的性質(zhì)（a10>a21）结执，找到并實現(xiàn)這些性質(zhì)就找到了最優(yōu)解，這是反向求解法艾凯。
