Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

盛最多水的容器 #5

Open
louzhedong opened this issue Apr 24, 2018 · 0 comments
Open

盛最多水的容器 #5

louzhedong opened this issue Apr 24, 2018 · 0 comments

Comments

@louzhedong
Copy link
Owner

louzhedong commented Apr 24, 2018

题目

出处:LeetCode 算法第11题

给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。画 n 条垂直线,使得垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

**注意:**你不能倾斜容器,n 至少是2。

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.

分析

经典的木桶问题,能盛水的多少取决于短边的高度。

解答

方法1、

暴力破解,使用时间复杂度为O(n^2)的算法

var maxArea = function (height) {
  var maxArea = 0;
  var low = 0, high = height.length;
  for (var i = low; i < high - 1; i  ) {
    for (var j = i   1; j < high; j  ) {
      var result = 0;
      if (height[i] < height[j]) {
        result = (j - i) * height[i];
      } else {
        result = (j - i) * height[j]
      }
      if (result > maxArea) {
        maxArea = result
      }
    }
  }

  return maxArea;
};
解法2、

从数组两边向中间靠拢,记录每一次计算的面积,当左边小于右边时,使左边向右移动,因为此时右边不管怎么动,左边已经决定了面积的大小,除非右边移动后比左边还要小,但这是获取的面积只会更小。反之亦然。只需一遍遍历即可,时间复杂度为O(n)

var maxArea2 = function (height) {
  var maxArea = 0;
  var low = 0, high = height.length - 1;
  while (low < high) {
    maxArea = Math.max(maxArea, Math.min(height[low], height[high]) * (high - low));
    if (height[low] < height[high]) {
      low  ;
    } else {
      high--;
    }
  }
  return maxArea;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant