題目：
Given?n?non-negative integers?a1,?a2, ...,?an, where each represents a point at coordinate (i,?ai).?n?vertical lines are drawn such that the two endpoints of line?i?is at (i,?ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and?n?is at least 2.
大致意思如下：
有（1,a1) (2,a2)....(n,an)幾個點，現(xiàn)在向x軸做垂線驻呐，其中兩條垂線與所夾的一段x軸形成一個凹槽灌诅，可作為容器盛水，問盛水的最大的體積為多少暴氏？如下圖：
解題：
我首先的想法是兩個for循環(huán)嵌套延塑，嗯，比較蠢答渔，代碼如下：
class Solution {public: int maxArea(vector& height) {
? ? ? ? int contain = 0;
? ? ? ? int temp = 0;
? ? ? ? for(int i = 0; i < height.size() - 1; ++i)
? ? ? ? {
? ? ? ? ? ? for(int j = i + 1; j < height.size(); ++j)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? temp = (height[i] <= height[j]) ? height[i] : height[j];
? ? ? ? ? ? ? ? temp = temp * (j - i);
? ? ? ? ? ? ? ? contain = (temp > contain) ? temp : contain;
? ? ? ? ? ? }? ? ? ? ?
? ? ? ? }
? ? ? return contain;
? ? }
};
submission后奇跡出現(xiàn)了关带，49個testcase通過48個，然而沼撕，最后一個爆了宋雏，time limit exceed，我認為應該是太蠢务豺，效率太低磨总，然后爆掉了，畢竟兩個for嵌套～
于是笼沥，在我看了其他大神的攻略后蚪燕，發(fā)現(xiàn)自己果然蠢，這個題可以這么想：
1. 每次計算體積時一定以最短長度作為高
2. 如果左邊低于右面的話奔浅，右邊的橫坐標越大越好
本著以上兩點馆纳，我們可以用兩個計數(shù)器，i初始為最左邊汹桦，j初始為最右邊鲁驶，if height[i] < height[j], 那么就非常開心了，因為在這種情況下舞骆，此時一定體積最大（
因為高一定钥弯，此時最長）径荔，那么接下來我們就可以進行i右移一位了，反過來情況下脆霎，j就要左移一位了总处，代碼如下：
class Solution {public: int maxArea(vector& height) {
? ? ? ? int contain = 0;
? ? ? ? int temp = 0;
? ? ? ? int i = 0;
? ? ? ? int j = height.size() -1 ;
? ? ? ? if (height.size() == 2)
? ? ? ? ? ? contain = (height[0] < height[1]) ? height[0] : height[1];
? ? ? ? else {
? ? ? ? ? ? while(i < j)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (height[i] <= height[j])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? temp = height[i] * (j - i);
? ? ? ? ? ? ? ? ? ? contain = (temp > contain) ? temp : contain;
? ? ? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? temp = height[j] * (j - i);
? ? ? ? ? ? ? ? ? ? contain = (temp > contain) ? temp : contain;
? ? ? ? ? ? ? ? ? ? j--;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }? ? ? ? ? ? ?
? ? ? return contain;
? ? }
};
嗯～通過了，雖然only beats 29.18% cpp 且代碼有點冗余绪穆，但這個思路先記下咯～
