j

jaryue

V1

2023/03/29阅读:13主题:默认主题

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
}
  1. 使用双指针法遍历数组,,定义i,ji放在开头,j放在结尾,
for i, j := 0len(height)-1; i < j; {//申请两个指针,一个i放在开头,j放在结尾
  //计算,赋值,指针移动操作
 }
  1. 计算,赋值,指针移动操作
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 := 0len(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 := 0len(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


分类:

后端

标签:

Golang

作者介绍

j
jaryue
V1