127 - 11 盛最多水的容器

题目

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

说明：你不能倾斜容器，且 n 的值至少为 2。

img

示例:

输入: [1,8,6,2,5,4,8,3,7] 输出: 49

解答

怎么感觉就只能硬算

看了题解发现还能双指针

https://leetcode-cn.com/problems/container-with-most-water/solution/shuang-zhi-zhen-fa-zheng-que-xing-zheng-ming-by-r3/

思路就是，头尾两个指针，计算一下面积。移动其中高度小的那一个。

因为移动高的那个，面积必然减小，移动小的，有可能变大。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height)-1
        ans = 0
        while left < right:
            temp = (right - left)*min(height[left], height[right])
            if temp > ans:
                ans = temp
            if height[left] > height[right]:
                right -= 1
            else:
                left += 1
        return ans

Runtime: 168 ms, faster than 7.64% of Python3 online submissions for Container With Most Water.

Memory Usage: 15.3 MB, less than 5.26% of Python3 online submissions for Container With Most Water.

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func maxArea(height []int) int {
    var left, ans int
    right := len(height) - 1
    for left < right {
        temp := (right - left) * min(height[left], height[right])
        if temp > ans {
            ans = temp
        }
        if height[left] > height[right] {
            right--
        } else {
            left++
        }
    }
    return ans
}

Runtime: 12 ms, faster than 90.29% of Go online submissions for Container With Most Water.

Memory Usage: 5.6 MB, less than 46.67% of Go online submissions for Container With Most Water.

var maxArea = function(height) {
  let left = 0,
    right = height.length - 1,
    ans = 0
  while (left < right) {
    const temp = (right - left) * Math.min(height[left], height[right])
    if (temp > ans) {
      ans = temp
    }
    if (height[left] > height[right]) {
      right--
    } else {
      left++
    }
  }
  return ans
};

Runtime: 56 ms, faster than 87.22% of JavaScript online submissions for Container With Most Water.

Memory Usage: 35.4 MB, less than 90.91% of JavaScript online submissions for Container With Most Water.

另一种做法是直接在while里面判断

var maxArea = function(height) {
  let left = 0,
    right = height.length - 1,
    ans = 0
  while (left < right) {
    if (height[left] > height[right]) {
      let temp = height[right] * (right - left)
      ans = Math.max(temp, ans)
      right--
    } else {
      let temp = height[left] * (right - left)
      ans = Math.max(temp, ans)
      left++
    }
  }
  return ans
};

Runtime: 60 ms, faster than 70.80% of JavaScript online submissions for Container With Most Water.

Memory Usage: 35.7 MB, less than 42.42% of JavaScript online submissions for Container With Most Water.

反而变慢了。。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height)-1
        ans = 0
        while left < right:
            if height[left] > height[right]:
                temp = (right - left)*height[right]
                right -= 1
            else:
                temp = (right - left)*height[left]
                left += 1
            ans = max(temp, ans)
        return ans

Runtime: 148 ms, faster than 54.05% of Python3 online submissions for Container With Most Water.

Memory Usage: 15.6 MB, less than 5.26% of Python3 online submissions for Container With Most Water.

python反而变得更快了。。这是为啥。。