題目鏈接https://leetcode-cn.com/problems/container-with-most-water/
給定?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)成的容器可以容納最多的水谦疾。
說(shuō)明：你不能傾斜容器，且n的值至少為 2犬金。
圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]念恍。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為?49晚顷。
示例:
輸入:[1,8,6,2,5,4,8,3,7]?輸出:49
解析：
這個(gè)題目第一眼看下去就能夠想到n^2的算法峰伙，也就是暴力枚舉每?jī)筛樱?jì)算容納水量的多少该默，存一個(gè)最大值即可瞳氓。
但是這樣復(fù)雜度會(huì)有點(diǎn)高，可以稍微優(yōu)化一下栓袖。
優(yōu)化思路：
暴力枚舉改為枚舉到第一根柱子后匣摘，第二根柱子從最后一根開(kāi)始往前枚舉店诗，這樣的話在枚舉的過(guò)程中我們可以知道的是可能出現(xiàn)的最大值在慢慢變小，也就是一開(kāi)始i=1,j=10時(shí)音榜，兩個(gè)柱子之間隔著9個(gè)水柱庞瘸，可能的容水量最大值為第一根柱子的高度*9，但當(dāng)我們枚舉到j(luò)=9時(shí)囊咏，兩個(gè)柱子之間就只隔著8個(gè)水柱恕洲，可能的容水量最大值為第一根柱子的高度*8，所以只要我們當(dāng)前保存的最大值大于等于當(dāng)前可能的最大值時(shí)就可以剪枝了梅割。
代碼實(shí)現(xiàn)如下：
class Solution {
public:
? ? int maxArea(vector<int>& height) {
? ? ? ? int len=height.size();
? ? ? ? int result=0;
? ? ? ? for(int i=0;i<len;++i)
? ? ? ? {
? ? ? ? ? ? int imax=0;
? ? ? ? ? ? for(int j=len-1;j>i;--j)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? int num=0;
? ? ? ? ? ? ? ? if(height[j]>=height[i])
? ? ? ? ? ? ? ? ? ? num=height[i]*(j-i);
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? num=height[j]*(j-i);
? ? ? ? ? ? ? ? if(num>imax) imax=num;
? ? ? ? ? ? ? ? if(imax>=height[i]*(j-i)) break;
? ? ? ? ? ? }
? ? ? ? ? ? if(imax>result) result=imax;
? ? ? ? }
? ? ? ? return result;
? ? }
};
成功通過(guò)霜第，但是在用時(shí)上還能有很大優(yōu)化，雖然進(jìn)行了優(yōu)化户辞，但是這個(gè)算法的復(fù)雜度還是O(n^2)泌类，這個(gè)題目應(yīng)該是可以優(yōu)化成O(n)的。
