上一題：LeetCode第10題: isMatch(C語言）
思路：
1宿崭、基本解法
思路：建立兩層循環(huán)亲铡，分別計(jì)算數(shù)組兩個(gè)元素的乘積，與記錄的最大值比較
int maxArea(int* height, int heightSize) {
int max_area = 0;
for(int i = 0; i < heightSize; i++){
for(int j = heightSize - 1; j >= 0 && j > i; j--){
int min_height = 0;
if(height[i] - height[j] > 0){
min_height = height[j];
}
else{
min_height = height[i];
}
if((j - i) * min_height > max_area)
max_area = (j - i) * min_height;
}
}
return max_area;
}
自然葡兑，暴力破解的方法無法在LeetCode中檢查通過奖蔓。
2、改進(jìn)解法
思路：假設(shè)最優(yōu)解的左右下標(biāo)分別為 i讹堤，j 吆鹤，則面積area = min(height[i], height[j]) * (j - i)，這就要求 j 和 i盡量的遠(yuǎn)洲守，這就希望 i 離數(shù)組左邊界最近檀头， j 離數(shù)組右邊界最近轰异。最理想的情況自然是最優(yōu)解 i = 0，j = heightSize - 1暑始， 當(dāng)然面積還跟 min(height[i], height[j])有關(guān)搭独，我們可以從數(shù)組左右邊界開始遍歷數(shù)組，并比較記錄最大值廊镜。
假設(shè) 輸入height = [1,8,6,2,5,4,8,3,7]牙肝，heightSize = 9：
對于 i = 0，j = heightSize - 1 = 8嗤朴，height[i] <height[j]的時(shí)候
min(height[i], height[j]) = height[i] = 1配椭；則area = height[0] * （8 - 0）= 8；對于木桶左邊界為 i = 0時(shí)雹姊，假設(shè)右邊界還可能是比當(dāng)前的最右邊界 j = 8還小的下標(biāo)來作為最優(yōu)解存在
假設(shè)為k股缸，則k < j，對于面來說吱雏，new_area = min(height[i], height[k]) * (k - i)敦姻， 因?yàn)?k < j， 則若要new_area > area歧杏，必須要求min(height[i], height[k]) > min(height[i], height[j]) 镰惦，現(xiàn)在用反證法證明這種情況不存在：
情況一：當(dāng)height[k] > height[i]時(shí)，min(height[i], height[k]) = height[i]犬绒，new_area = height[i] * (k - i) 旺入，由于k < j，所以new_area < area凯力；
情況二：當(dāng)height[k] < height[i]時(shí)茵瘾，min(height[i], height[k]) = height[k]，new_area = height[k] * (k - i) 咐鹤，由于k < j龄捡，且height[k] < height[i]，所以new_area < area慷暂；
綜上聘殖，對于木桶左邊界為i = 0，height[i] <height[j]時(shí)行瑞，最大桶的面積的右邊界 j = heightSize - 1 = 8奸腺；
既然木桶左邊界為i = 0，height[i] <height[j]的情況已經(jīng)確定下來血久，則對于木桶的左邊界突照，可以從 i = 1開始重新進(jìn)入上述邏輯，比較height[i] 氧吐、height[j]的大小讹蘑，然后用min(height[i], height[j]) 作為桶一側(cè)的邊界的高度進(jìn)行計(jì)算末盔，然后用計(jì)算面積最大值和 i = 0時(shí)的記錄做比較即可。
結(jié)論：從數(shù)組兩側(cè)邊界向中間靠攏座慰，每次計(jì)算min(height[i], height[j]) 陨舱，不比回溯計(jì)算，進(jìn)而減少一層循環(huán)遍歷可解決版仔，時(shí)間復(fù)雜度為N游盲。
int maxArea(int* height, int heightSize){
int i = 0,j = heightSize - 1;
int area;
int result = 0;
while(i < j)
{
if(height[i] < height[j])
{
area=height[i] * (j - i);
int m = i + 1;
while(m < j && height[m] <= height[i]){
m++;
}
i = m;
}
else
{
area = height[j]*(j - i);
int n = j - 1;
while(n > i && height[n] <= height[j]){
n--;
}
j = n;
}
if(result < area)
result = area;
}
return result;
}
本系列文章，旨在打造LeetCode題目解題方法蛮粮，幫助和引導(dǎo)同學(xué)們開闊學(xué)習(xí)算法思路益缎，由于個(gè)人能力和精力的局限性，也會(huì)參考其他網(wǎng)站的代碼和思路然想，如有侵權(quán)莺奔，請聯(lián)系本人刪除。
下一題：LeetCode第12題: intToRoman(C語言）
