題目描述：

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.

給定n個(gè)非負(fù)整數(shù)a1，a2，...，an，其中每個(gè)代表坐標(biāo)（i，ai）處的一個(gè)點(diǎn)。 繪制n條垂直線，使得線i的兩個(gè)端點(diǎn)處于（i，ai）和（i，0）處。 找到兩條線，它們與x軸一起形成一個(gè)容器，以使容器包含最多的水。
注意：您不得傾斜容器。

?

/** 貪心算法：從兩邊開始向中間縮小;每一步比較左右邊界高度,高度小的那個(gè)向里走一步* * 這個(gè)貪心算法,為什么最優(yōu)解不會(huì)被錯(cuò)過？ 反證法 假設(shè)會(huì)被錯(cuò)過。* 假設(shè)最優(yōu)解是橫坐標(biāo)為x1,x2(x2在右邊)的這兩個(gè)點(diǎn)組成的* 只考慮掃描到x2時(shí),x1被錯(cuò)過的情況(x2被錯(cuò)過同理)：* 被錯(cuò)過指的是 當(dāng)右指針向左掃描經(jīng)過x2之后,左指針還在x1的左邊P處時(shí),x1被錯(cuò)過。* * 情況一 x2>p: x2會(huì)被保留,然后左指針向右移動(dòng)到x1,x1不會(huì)被錯(cuò)過* 情況二 x2<p: 小情況一：height[p]>height[x1] 則最優(yōu)解為 p,x2而不是 x1,x2。 假設(shè)不成立* 小情況二：p<=x1 最優(yōu)解還是p,x2。 假設(shè)不成立* //因?yàn)閤2比p和x1都小,所以容器高度取決于x2,而p比x1偏左,所以p,x2比x1,x2面積大* * */public int maxArea(int[] height) {if(height.length<=2) return 0;int left=0,right=height.length-1;int maxArea=0;while(left<right) {int area = Math.min(height[left],height[right])*(right-left);maxArea = Math.max(maxArea, area);if(height[left]<=height[right]) {left++;}else {right--;}}return maxArea;}

?

轉(zhuǎn)載于:https://www.cnblogs.com/whu-gbf/p/9173582.html

總結(jié)

以上是生活随笔為你收集整理的container-with-most-water（最大蓄水问题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。