LeetCode 11. Container With Most Water

11. Container With Most Water

Difficulty: medium

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.

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:

Input: [1,8,6,2,5,4,8,3,7] Output: 49

这题看了第一眼, dp, 绝对是dp, 但是因为菜是原罪所以不会写.

先写个暴力:
1st Version:

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

Rate:
Runtime: 1264 ms, faster than 8.21% of C++ online submissions for Container With Most Water.
Memory Usage: 9.7 MB, less than 97.94% of C++ online submissions for Container With Most Water.

很显然, 写算法优先不能想着去暴力模拟, 人们更希望拿空间去换时间.

2nd Version:

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

Rate:
Runtime: 20 ms, faster than 68.17% of C++ online submissions for Container With Most Water.
Memory Usage: 9.7 MB, less than 94.85% of C++ online submissions for Container With Most Water.

讨论区剽的方法.
思路大致说一下, 其实很简单, 从两头开始算, i和j是”筷子”索引. 主要就是关于这俩怎么更新的问题. 其实这个问题也很简单, height[i]和height[j]谁小谁更新, 为啥呢, 因为area = min(height[i], height[j]) * (j - i), 既然(j - i)要不断缩小, 如果想要在更新之后还能找到更大的, 只能让min(height[i]), height[j]更大, 具体怎么更大, 就不用多赘述了吧.