Container With Most Water(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.

Example

Given [1,3,2], the max area of the container is 2.

解题思路

方法一

枚举左、右边界，更新答案。
时间复杂度 O(n^2).

方法二

two pointer. 也就是双指针
时间复杂度 O(n)

参考代码

方法一

class Solution {
public:
    /**
     * @param heights: a vector of integers
     * @return: an integer
     */
    int maxArea(vector<int> &heights) {
        // write your code here
        int n = heights.size();
        int ans = 0;
        for (int i = 1; i < n; ++ i) {
            for (int j = 0; j < i; ++ j) {
                if (heights[j] >= heights[i]) {
                    ans = max(ans, (i - j) * heights[i]);
                    break;
                } else {
                    ans = max(ans, (i - j) * heights[j]);
                }
            }
        }

        return ans;
    }
};

方法二

class Solution {
public:
    /**
     * @param heights: a vector of integers
     * @return: an integer
     */
    int maxArea(vector<int> &heights) {
        // write your code here
        int n = heights.size();
        if (n <= 1) return 0;
        int ans = 0;
        int l = 0, r = n - 1;
        while (l < r) {
            ans = max(ans, min(heights[l], heights[r]) * (r - l));
            if (heights[l] < heights[r]) {
                ++ l;
            } else {
                -- r;
            }
        }

        return ans;
    }
};