011.md

Container With Most Water

题目：

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.

思路： 暴力是过不了，两个for循环会超时间。

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

1. 为了计算最大装水量C = L * H，H为高度，L为长度。也就是说找出C的最大值,C的最大值取决于H和L。使用一个变量max保持当前最容量
   
2. H取决于两条线的最小值。设置两个索引i，j分别初始为第一个元素的索引和最后一个元素的索引，L=j-i，这两条直线产生容量为temp = L* min(height[i],height[j]) 。
   
3. 假设i，j表示的直线a和b，且a更短，则当前容量即为a能产生容量的最大值，因为无论b之前(j减少)的直线比a长或比a短，a产生的容量都小于temp，如果比a长，那么H还是不变(取决于短的直线a)，而L却变小了(j减小了);如果比a短，那么H和L都变小了，所以temp即为当前a所能产生的最大容量，相当于a已经遍历了一遍。如果b更短，同理。更新max
   
4. 这里假设a更短，a产生的最大容量已知，为了找出最大的容量，i向前移动1。当前i表示的直线为c，如果c比a更短，那么产生的容量比a产生的最大值肯定要小，因相对于上一步L和H同时变小了，所以i继续向前移动1,当前i表示的线为d，如果d比b长，那么才有可能产生更大的值(L虽然变短，但H变大)，计算temp = L* min(height[i],height[j]) ，如果比max大，更新max。
   
5. 同理继续这样运行下去直到i==j。i和j所表示的直线的长度谁更短 则谁移动。

代码：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int sz = height.size();
        int max = 0;
        int i = 0,j=sz-1;//i为第一个高度的索引，j为之后一个高度的索引
        while(i!=j){
            int temp = 0;
            int l = j-i;//两条线之间的长度
            //当前的最大值为 较小高度的值乘以两条线之间的长度。较短线的索引移动，i向前移动，j向后移动。
            temp = height[i]<=height[j]? height[i++]*l :  temp = height[j--]*l;
            if(temp>max) max = temp;
        }
        return max;
    }
};