給定 n 個非負整數 a1，a2孤页，...，an涩馆，每個數代表坐標中的一個點 (i, ai) 行施。在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)魂那。找出其中的兩條線蛾号，使得它們與 x 軸共同構成的容器可以容納最多的水。
說明：你不能傾斜容器涯雅，且 n 的值至少為 2鲜结。
圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49精刷。
輸入: [1,8,6,2,5,4,8,3,7]
輸出: 49
思路一：暴力的雙重循環(huán)
時間復雜度為,在數據量較大的時候拗胜，性能很差
思路二：雙指針
- 核心思想： 減少循環(huán)的核心思路是省去沒有必要的遍歷，并且確保所需的答案一定能被遍歷到怒允。容器的盛水量取決于容器的底和容器較短的那條高埂软。 容器高度較大的一側的移動只會造成容器盛水量減小，所以應當移動高度較小一側的指針纫事，并繼續(xù)遍歷仰美，直至兩指針相遇 。
- 分析：主要的困惑在于如何移動雙指針才能保證最大的盛水量被遍歷到假設有左指針left和右指針right儿礼，且left指向的值小于right的值，假如我們將右指針左移庆寺，則右指針左移后的值和左指針指向的值相比有三種情況：
- 右指針指向的值大于左指針這種情況下蚊夫，容器的高取決于左指針，但是底變短了懦尝，所以容器盛水量一定變小.
- 右指針指向的值等于左指針這種情況下知纷，容器的高取決于左指針，但是底變短了陵霉，所以容器盛水量一定變小.
- 右指針指向的值小于左指針這種情況下琅轧，容器的高取決于右指針，但是右指針小于左指針踊挠，且底也變短了乍桂，所以容量盛水量一定變小了.
std:max
c++ code: AC
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.capacity() - 1;
int maxArea = 0;
while (left < right)
{
maxArea = max(maxArea, (right - left)*min(height[left], height[right]));
if (height[left] < height[right])
left++;
else
right--;
}
return maxArea;
}
};
測試框架：
void trimLeftTrailingSpaces(string &input) {
input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
return !isspace(ch);
}));
}
void trimRightTrailingSpaces(string &input) {
input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
return !isspace(ch);
}).base(), input.end());
}
vector<int> stringToIntegerVector(string input) {
vector<int> output;
trimLeftTrailingSpaces(input);
trimRightTrailingSpaces(input);
input = input.substr(1, input.length() - 2);
stringstream ss;
ss.str(input);
string item;
char delim = ',';
while (getline(ss, item, delim)) {
output.push_back(stoi(item));
}
return output;
}
int main() {
string line;
while (getline(cin, line)) {
vector<int> height = stringToIntegerVector(line);
int ret = Solution().maxArea(height);
string out = to_string(ret);
cout << out << endl;
}
return 0;
}
