題目
給定 n 個非負(fù)整數(shù) a1，a2删豺，...共虑，an，每個數(shù)代表坐標(biāo)中的一個點(diǎn) (i, ai) 呀页。在坐標(biāo)內(nèi)畫 n 條垂直線妈拌，垂直線 i 的兩個端點(diǎn)分別為 (i, ai) 和 (i, 0)。找出其中的兩條線蓬蝶，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水尘分。
說明：你不能傾斜容器，且 n 的值至少為 2丸氛。
image.png
示例:
輸入: [1,8,6,2,5,4,8,3,7]
輸出: 49
思路
1.暴力搜尋法
int maxArea(vector<int>& height) {
int result;
for (int i = 0; i < height.size() - 1; i ++)
{
for(int j = i + 1; j < height.size(); j ++)
{
result = max(result, min(height[i], height[j]) * (j - i));
}
}
return result;
}
2.雙指針法
建立兩個指針分別指向數(shù)組的第一位和最后一位培愁。容器的容積既和寬度有關(guān)，也和容器的高度有關(guān)缓窜，如果寬度逐漸縮小定续，但是高度可以增加的話同樣有可能增加容器的容積谍咆。因此每次移動高度較低的指針對應(yīng)的值。
int maxArea2(vector<int>& height)
{
int result;
int left = 0, right = height.size() - 1;
while (right > left)
{
result = max(result, (right - left) * min(height[right], height[left]));
(height[left] <= height[right]) ? (left++) : (right--);
}
return result;
}
主函數(shù)
int main(int argc, char* argv[])
{
vector<int> test = { 1,8,6,2,5,4,8,3,7 };
int result = Solution().maxArea2(test);
cout << result ;
system("pause");
}
