leetcode11盛水最多的容器

leetcode 11

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。 示例 2：

输入：height = [1,1] 输出：1

提示：

n == height.length 2 <= n <= 105 0 <= height[i] <= 104

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/container-with-most-water 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

法1双指针\

1. 定义ismin函数用于寻找更小的数值

// 方法更小的数
func ismin(i, j int) int {
 if i > j {
  return j
 }
 return i
}

2. 使用双指针法遍历数组,,定义i,ji放在开头,j放在结尾,

for i, j := 0, len(height)-1; i < j; {//申请两个指针,一个i放在开头,j放在结尾
  //计算,赋值,指针移动操作
 }

3. 计算,赋值,指针移动操作

if (j-i)*ismin(height[i], height[j]) > h {//如果结果大于h,则给h赋值
   h = (j - i) * ismin(height[i], height[j])
  }
  if height[i] > height[j] {//较小的一个指针移动
   j--
  } else {
   i++
  }

执行结果

法1

// 方法更小的数
func ismin(i, j int) int {
 if i > j {
  return j
 }
 return i
}
// 双指针
func maxArea(height []int) int {
 h := 0//用于储存最大的返回结果
 for i, j := 0, len(height)-1; i < j; {//申请两个指针,一个i放在开头,j放在结尾
  if (j-i)*ismin(height[i], height[j]) > h {//如果结果大于h,则给h赋值
   h = (j - i) * ismin(height[i], height[j])
  }
  if height[i] > height[j] {//较小的一个指针移动
   j--
  } else {
   i++
  }
 }
 return h//返回最大的容器结果
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 72 ms , 在所有 Go 提交中击败了 54.93% 的用户 内存消耗： 8.1 MB , 在所有 Go 提交中击败了 80.42% 的用户 通过测试用例： 61 / 61

法2

优化

func maxArea(height []int) int {
 h := 0
 for i, j := 0, len(height)-1; i < j; {
  if height[i] > height[j] {//将不必要的函数ismin取消掉.用两个if语句来代替,以减少时间和空间的浪费
            if height[j]*(j-i)>h{h=height[j]*(j-i)}
   j--
  } else {
            if height[i]*(j-i)>h{h=height[i]*(j-i)}
   i++
  }
 }
 return h
}

执行用时： 64 ms , 在所有 Go 提交中击败了 93.32% 的用户 内存消耗： 8.7 MB , 在所有 Go 提交中击败了 23.69% 的用户 通过测试用例： 61 / 61

法3