凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 11. Container With Most Water

分类:algorithm| 发布时间:2016-07-01 08:11:00


题目

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.

题意

找出非负数组中的两个点 (i, ai) 与 (j, aj),使其与 x 轴形成的容器能装最多水。

解法

影响容器的容量的因素有两个,一个是 i 与 j 之间的距离,距离越大越好, 一个是 min(ai, aj) 这个值也是越大越好。 先给出解法:

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

        return maxArea;
    }
};

为什么这种解法是对的呢,假设我们有个长度为 6 的数组, 那么要解出最大值的直接方法是算法任意两个距离的大小, 然后取其最大值。 由于 i 和 j 不能取同样的值,因此 i 和 j 相同的情况不用算,我们用 'x' 来标记。

    1 2 3 4 5 6
  1 x
  2 x x
  3 x x x
  4 x x x x
  5 x x x x x
  6 x x x x x x

假设 i 为行号,j 为列号。 我们首先计算 i 和 j 最大的情况,我们用 'o' 标记算出的结果,假设 a6 大于 a1。 那么 (1, a1) 和 (6, a6) 的结果等于 (6 - 1) * a1。 同时 a1 和 a2..a5 的值都不用算了,因为肯定比 a1 和 a6 的值小。 首先是长度 (j - i) 肯定是变小的,其次是高度肯定是不必 a1 高。 我们用 '-' 或 '|' 来标记不用算的情况:

    1 2 3 4 5 6
  1 x - - - - o
  2 x x
  3 x x x
  4 x x x x
  5 x x x x x
  6 x x x x x x

将 i 往前移动,对比 a2 和 a6 的大小,如果是 a2 比 a6 小,情况与上一步一样。 我们这里假设 a2 比 a6 大。相似地由于 a6 < a2,因此 a2 与 a3..a5 的面积肯定比 a6 小。

    1 2 3 4 5 6
  1 x ------- o
  2 x x       o
  3 x x x     |
  4 x x x x   |
  5 x x x x x |
  6 x x x x x x

然后将 j 减 1,对比 a2 和 a5 的大小。 通过这样的方法,我们只用算出尽量少的情况(也就是标记为 ‘o' 的情况)。 然后取其最大值就是解。这个算法的复杂度为 O(n)。