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

?

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

方法一:暴力解法

class Solution {
public:
    int maxArea(vector& height) {
        	
            int len = height.size();
            int max = 0;
            for(int i=0; i max) {
                        max = temp;
                    }
                }
            return max;
    }
};

Complexity Analysis

  • Time complexity :?O(n^2). Calculating area for all ??n(n?1)??/2 height pairs.
  • Space complexity : O(1). Constant extra space is used.?

?

方法二:利用两个指针进行逼近

? ?我们取两个指针,一个在开头,一个在数组的末尾,构成行的长度。 此外,我们维持一个变量maxarea来存储到目前为止获得的最大面积。 在每一步,我们找出它们之间形成的区域,更新maxarea并将指向较短竖线的指针向另一端移动一步。

? ?举个例子,对于(1,6)的情况,如果位置1的竖线长度小于位置6的长度,那么对于位置1而言,它的最大面积已经求出来了(因为一个梯形的面积是由其底长度与两个高中较短的高决定的),因此右边的线如何移动是无所谓的。也就是说(1,2)(1,3)(1,4)(1,5)的情况都可以不用考虑。下一步就移动左边的线到位置2。如果位置2的长度大于位置6,那么位置6的最大面积已经求出来了。同理左边的线再怎么移动都无所谓。于是再下一步就移动右边的线到位置5。以此类推。

??

class Solution {
public:
    int maxArea(vector& height) {
            int len = height.size();
            if (len <= 1) {
                return 0;
            }
            int max_area = 0, left = 0, right = len - 1;

            while (left < right) {
                int area = (right - left) * min(height[left], height[right]);
                max_area = max(max_area, area);

                if (height[left] <= height[right]) {
                    ++left;
                }
                else {
                    --right;
                }
            }
            return max_area;
    }
};

Complexity Analysis

  • Time complexity :?O(n). Single pass.

  • Space complexity :?O(1) Constant space is used.

?

原文链接:加载失败,请重新获取