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

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

示例：

輸入：[1,8,6,2,5,4,8,3,7]
輸出：49

【解答思路】

1. 貪心算法 暴力

求解是要獲得最大面積，即以第一個(gè)面積值作為假定的最大面積，然后不斷的用更大的值刷新，直到將所有的面積都計(jì)算完畢。
S(i,j)=min(h[i],h[j])×(j?i)
時(shí)間復(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. 雙指針

時(shí)間復(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. 雙指針 相清楚移動(dòng)哪一個(gè)可以優(yōu)化

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

image.png