11. 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.

Difficulty: Medium

求最多能装多少水,如果没看懂的话,看下下图

这道题我们需要定义i,j俩个指针分别指向数组的左右两端,然后两个指针向中间搜索,这里要求(j-i) * min(height[i] ,height[j])的最大值.每次移动要比较保存最大值.

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

小优化一些, 如果一次移动后, 如果下一个高度与上一个相同,那么直接移动就可以了, 不必比较

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