container-with-most-water

Posted on | Post modified:

Find two lines, which together with x-axis forms a container, such that the container contains the most water.

  1. 问题
    英文详细描述见链接container-with-most-water
    主要题意是：给定位于x轴上方的n个点，过这n个点作与x轴的垂线作为隔板。要求找到两个点，它们的隔板与x轴形成的水箱能够存储的水最多。

  2. 分析

    • 思路一
      从x坐标最大和最小的两个点开始，对于高度小的那个点，它与所有其他点能构成的水箱的最大面积取决于它的高度和另一点和它在x方向上的距离，这时候最大面积就是和另外一个点配对构成的。随后该点被剔除，对剩下的点列进行同样的操作，若后面的最大面积超过原来的结果，就更新最大面积的值。这种解法的复杂度为O(N)。
    • 思路二
      先对所有点按照高度由小到大进行排序，并记录它们的索引值。由最小的高度值开始，求取它与其他各点横坐标之差的最大值，计算与它相关的最大面积。随后对剩下的点列进行相同的操作，同时更新最大面积值。这种解法的复杂度为O(NlogN)。

  3. code
    (1)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {
    public:
        int maxArea(vector<int>& height) {
            int max_area = 0, start = 0, end = height.size()-1;
            while (start < end) {
                max_area = max(max_area, (end - start)*(height[start] < height[end] ? height[start++] : height[end--]));
            }
            return max_area;
        }
    };

    (2)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class Solution {
    public:
        template <typename T>
        vector<int> sort_index(vector<T> &A) {
            vector<int> index(A.size());
            iota(index.begin(), index.end(), 0);
            sort(index.begin(), index.end(), 
                [&A](int i1, int i2) {return A[i1] < A[i2];});
            sort(A.begin(), A.end());
            return index;
        }

        int max_range(const vector<int>& index, int i) {
            int match_i =  *max_element(index.begin() + i, index.end(),
                            [&index, i](int i1, int i2) {return abs(index[i] - i1) < abs(index[i] - i2);});
            return abs(index[i] - match_i);
        }
        
        int maxArea(vector<int>& height) {
            vector<int> index = sort_index(height);
            int max_area = 0;
            for (int i = 0; i < height.size(); i++) {
                int new_area = height[i] * max_range(index, i);
                max_area = max_area < new_area ? new_area : max_area;
            }
            return max_area;
        }
    };