Container With Most Water

Given n non-negative integers a₁, a₂, …, a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) 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.

tag:

9/26/2015 update

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

暴力搜，o(n^2)超时。

class Solution {
public:
    int maxArea(vector<int> &height) {
        int maxCapacity = 0;
        for(vector<int>::iterator start = height.begin(); start != height.end(); start++){
            for(vector<int>::iterator end = start + 1; end != height.end(); end++){
                int minHeight = min(*start, *end);
                int thisCapacity = minHeight * distance(start, end);
                if (thisCapacity > maxCapacity){
                    maxCapacity = thisCapacity;
                }
            }
        }
        return maxCapacity;
    }
};

先排序，然后剪枝。最坏情况o(n^2)，不幸test case中有最坏情况(1, 2, 3, 4, 5, 6…)超时。

class point{
public:
    int height;
    int x;
    point(int x, int h) : x(x), height(h){}
};
class Cmp{
public:
  bool operator()(point a, point b){
      return a.x > b.x;
  }  
};
class Solution {
public:
    int maxArea(vector<int> &height) {
        int maxCapacity = 0;
        vector<point> data;
        for(int i = 0; i < height.size(); i++){
            data.push_back(point(i, height[i]));
        }
        sort(data.begin(), data.end(), Cmp());
        for(vector<point>::iterator start = data.begin(); start != data.end(); start++){
            if((*start).height * max((int)(data.size() - (*start).x - 1), (*start).x) < maxCapacity){
                return maxCapacity;
            }
            for(vector<point>::iterator end = start + 1; end != data.end(); end++){
                if((*end).height * max((int)(data.size() - (*end).x - 1), (*end).x) < maxCapacity){
                    break;
                }
                int minHeight = min((*start).height, (*end).height);
                int thisCapacity = minHeight * distance(start, end);
                if (thisCapacity > maxCapacity){
                    maxCapacity = thisCapacity;
                }
            }
        }
        return maxCapacity;
    }
};

再次优化，这题和直方图中最大矩形的那道题很类似。

我用left储存原数组中左到右递增的序列，用right储存原数组中从右到左递增的序列。在两个数组中遍历。

最坏情况o(n^2)。AC了。

class node{
public:
   int x;
   int height;
   node(int x, int h): x(x), height(h){}
};
class Solution {
public:
    int maxArea(vector<int> &height) {
        int maxCapacity = 0;
        vector<node > left;
        vector<node > right;
        int length = height.size();
        left.push_back(node(0, height[0]));
        right.push_back(node(length - 1, height[length - 1]));
        for(int i = 0; i < length; i++){
            if(left.back().height < height[i]){
                left.push_back(node(i, height[i]));
            }
            if(right.back().height < height[length - i - 1]){
                right.push_back(node(length - i - 1, height[length - i - 1]));
            }
        }
        for(int i = 0; i < left.size(); i++){
            int idxl = left[i].x;
            for(int j = 0; j < right.size(); j++){
                int idxr = right[j].x;
                if(idxr <= idxl){
                    break;
                }
                int thisCapacity = min(left[i].height, right[j].height) * (idxr - idxl);
                if(thisCapacity > maxCapacity){
                    maxCapacity = thisCapacity;
                }
            }
        }
        return maxCapacity;
    }
};

但是看了解答，其实有更好的o(n)的方法。

维护两个指针，一个放在数组开头，一个放在数组末尾。

两个指针都向中间靠拢，每次移动height小的那个指针。因为height小的是影响盛水量的瓶颈。

class Solution {
public:
    int maxArea(vector<int> &height) {
        int maxCapacity = 0;
        int start = 0;
        int end = height.size() - 1;
        while(start < end){
            int minHeight = min(height[start], height[end]);
            int thisCapacity = minHeight * (end - start);
            if (thisCapacity > maxCapacity){
                maxCapacity = thisCapacity;
            }
            if(minHeight == height[start]){
                start++;
            }
            else{
                end--;
            }
        }
        return maxCapacity;
    }
};