【問題描述】11.盛最多水的容器

給你 n 個非負(fù)整數(shù) a1，a2，...，an，每個數(shù)代表坐標(biāo)中的一個點 (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。示例：輸入：[1,8,6,2,5,4,8,3,7] 輸出：49

【解答思路】

1. 貪心算法 暴力

求解是要獲得最大面積，即以第一個面積值作為假定的最大面積，然后不斷的用更大的值刷新，直到將所有的面積都計算完畢。
S(i,j)=min(h[i],h[j])×(j?i)
時間復(fù)雜度：O(N^2) 空間復(fù)雜度：O(1)

class Solution {public int maxArea(int[] height) {int area = 0;for (int i = 0; i < height.length - 1; i++) {int iValue = height[i];for (int j = i + 1; j < height.length; j++) {int jValue = height[j];int hValue = Math.min(iValue, jValue);int lValue = j - i;int aValue = lValue * hValue; if (aValue > area) {area = aValue;}}}return area;}}

2. 雙指針

時間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

public int maxArea(int[] height) {int area = 0;for (int i = 0; i < height.length - 1; i++) {int iValue = height[i];for (int j = i + 1; j < height.length; j++) {int jValue = height[j];int hValue = Math.min(iValue, jValue);int lValue = j - i;int aValue = lValue * hValue; if (aValue > area) {area = aValue;}}}return area;}}

【總結(jié)】

1. 暴力法思考 逐漸優(yōu)化

2. 雙指針 相清楚移動哪一個可以優(yōu)化

3.思路一開始找兩個最大值，由內(nèi)推到外，過于復(fù)雜，應(yīng)及時放棄思路

總結(jié)

以上是生活随笔為你收集整理的[Leedcode][JAVA][第11题][盛最多水的容器][双指针][贪心]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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