Container With Most Water ！！！！！！！！！！

Q:

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

 

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

 

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

A:

----------------------------------第三遍-----------------

上面都是O(n^2)的复杂度，但是，有个O(n)的复杂度的。

下面是分析 （引用）

find the maximum value of (i-j)*min( a_i , aj  ).

Set two pointers, point to begin and end. Move the pointer which points to the smaller element in array.  因为我们一开始都已经是最大的间距了。 因此左右两个pointer中，小的那个，以及不可能有更好的相乘结果了. 因此就可以调整它

https://leetcode.com/problems/container-with-most-water/solutions/5139915/video-simple-two-pointer-solution/

Proof:
 Because the contain volume is decided by the shorter line between two.
Since a_i is lower than aj,  so there will be no jj < j that make the area from i, jj is greater than area from i,j so the maximum area that can benefit from i is already recorded.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1, res = 0;
        while (i < j) {
            res = max(res, (j - i) * min(height[i], height[j]));
            if (height[i] <= height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return res;
    }
};

------------------------------------------- 第4遍。-------------------

考虑到，对于左边的bar， 如果左边有个更高的，就不需要保留它。  因此所生成的 potential left bar， 只会是从左向右 逐个增加

同理，对于右边的bar，从后往前看， 如果后面有比他高的， 就不需要考虑它了。

最后再全部找找对应的解决方案

class Solution {

public:

int maxArea(vector<int>& height) {

int n = height.size();

// for left side, ignore any bar is lower then a bar on its left

vector<pair<int, int>> L; // for a pair, 0 is for index, 1 for value

for(int i =0; i < n; i++ ){

if(i==0 || height[i] > L.back().second ){

L.push_back(pair{i,height[i]});

}

}

// for right side, ignore any bar is lower then a bar on its right

vector<pair<int, int>> R;

for(int j =n-1; j>=0 ; j-- ){

if(j== n-1 || height[j] > R.back().second ){

R.push_back(pair{j, height[j]});

}

}

// check all possible combinations

int res = 0;

for(auto& pl : L){

for(int i =0; i< R.size(); i++){

if(R[i].first <= pl.first)

break;

res = max(res, (R[i].first - pl.first) * min(R[i].second, pl.second));

}

}

return res;

}

};

思路： 就是 一个个往上加line。  *****************但是这样会超时＊＊＊＊＊＊＊

public class Solution {
   public int maxArea(int[] height) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int maxWater = 0;
        int n = height.length ;
        if(n<=1 ) {
            return maxWater;
        }
        for(int i =1;i< n ;i++){
            int maxEndHere = maxEndAtI(height,i,maxWater);
            maxWater = maxWater>maxEndHere?maxWater:maxEndHere;
        }
        return maxWater;
    }
    private int maxEndAtI(int[] height, int i, int maxWater){
        // return the max water that returns at current position
        if( height[i] * i  < maxWater||  height[i] == 0 ){  // height[i] is too low to exceed former maxWater
            return 0;
        }
        //start from the possible left position
        int leastLength = maxWater/height[i];
        int leftLineMostRighPos = i - leastLength;
        int curMaxWater = maxWater;
        for(int j= leftLineMostRighPos; j>=0;j--){
            int curWater = Math.min(height[j],height[i])*(i-j);
            if(curMaxWater < curWater){
                curMaxWater = curWater;
            }
        }
        return curMaxWater;
    }
}

Mistakes:
1:又一次出现了，除零的问题。。 ╮(╯▽╰)╭

-------------------第二遍----------
1： 题意理解错误， 应该是 2条line，  而不是bar，  因此，即使输入是【1,1】的时候， 也可以盛1单位的水。
2： 题意理解错误，  两条line，中间即使是有个比他们都高的， 也不碍事。
例如，输入是：[1,2,1] 的时候，输出应该是2、

3:   哎， again，  出现了除零的问题。   ----------Tiger， 记住，只要是出现除数， 就要检查其值是否为0.


Learned:
1: 即使是int类型的变量， 如果要 调用的话，也需要事先initialize。