[路飞]_leetcode-11-盛最多水的容器

本文涉及的产品
容器镜像服务 ACR,镜像仓库100个 不限时长
简介: leetcode-11-盛最多水的容器

网络异常,图片无法展示
|


[题目地址][B站地址]


给你 n 个非负整数 a1,a2,...,a``n,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai)(i, 0) 。找出其中的两条线,使得它们与 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
复制代码


示例 3:


输入: height = [4,3,2,1,4]
输出: 16
复制代码


示例 4:


输入: height = [1,2,1]
输出: 2
复制代码


提示:


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


解题思路


最简单直接的方式就是双层循环,获取所有组合的容积,求得其中的最大值即为结果值。代码如下:


var resArea = function(height) {
  // 获取输入数组长度
  const len = height.length;
  // 初始化结果值为 0
  let res = 0;
  // 双层循环获取所有组合
  for(let i = 0;i<len-1;i++){
    const hi = height[i]
    for(let j = i+1;j<len;j++){
      // 尝试用当前组合容积更新结果值
      res = Math.res(res,Math.min(hi,height[j])*(j-i))
    }
  }
  // 返回结果值
  return res;
};
复制代码


但是这样的一版代码提交是超时的,时间复杂度是 O(n2) 的。


接下来我们想一个问题,如果说后边的柱子高度不大于当前柱子的高度,它可能会找到比当前柱子更大的容积组合吗?


答案是肯定找不到,所以可以对于以上代码进行一版优化。


记录当前找到最大值组合的左侧柱子,如果后续的柱子不高于当前柱子,则跳过循环。代码如下:


var maxArea = function(height) {
  // 获取输入数组长度
  const len = height.length;
  // 初始化左侧柱子下标,初始化结果值为 0
  let l,res = 0;
  // 双层循环获取所有组合
  for(let i = 0;i<len-1;i++){
    // 如果后续柱子不高于当前标记 l ,则肯定找不到更大的容器,直接跳过
    if(height[i]<=height[l]) continue;
    const hi = height[i]
    for(let j = i+1;j<len;j++){
      const area = Math.min(hi,height[j])*(j-i);
      // 如果当前组合更新了结果值,则将 l 更新为当前组合左侧柱子下标
      if(area>res) l = i,res = area;
    }
  }
  return res;
};
复制代码


这样的一版代码提交是可以通过的,但是时间复杂度依然为 O(n2)


所以接下来我们就要想到一个更有的解法。 首相容器的容积其实就是两根柱子高度的最小值 * 两根柱子之间的距离。


所以想要获取到更大的容积,就要让两根柱子的距离尽可能大,同时高度尽可能高。


所以我们可以采用两个指针,从两端开始。每次获取当前组合的容积,尝试更新结果值。


因为要让柱子尽可能的高,所以此时判断两根柱子的高度,如果左侧更矮,则左侧向右移动。如果右侧更矮,则右侧向左移动。直到两指针相遇。 这样就保证了可以获取到所有的尽可能高的组合,最后更新后的结果值,就是可以获取到的最大容积。。


动画演示


网络异常,图片无法展示
|


代码实现


var maxArea = function(height) {
  // 初始化结果值为 0
  let res = 0,
  // 定义两个指针
  l = 0,r = height.length-1;
  while(l<r){
    // 尝试用当前组合容积更新结果值
    const hl = height[l],hr = height[r];
    res = Math.max(res,Math.min(hl,hr)*(r-l))
    // 移动更矮的柱子
    if(hl<hr) l++
    else r--
  }
  // 返回结果值
  return res;
};
复制代码


至此我们就完成了 leetcode-11-盛最多水的容器


如有任何问题或建议,欢迎留言讨论!

相关文章
|
14天前
|
存储 容器
LeetCode刷题---11. 盛最多水的容器(双指针-对撞指针)
LeetCode刷题---11. 盛最多水的容器(双指针-对撞指针)
|
1月前
|
Java 容器
LeetCode题解-盛水最多的容器-Java
盛水最多的容器-Java
8 0
|
1月前
|
容器
LeetCode题:11. 盛最多水的容器
LeetCode题:11. 盛最多水的容器
14 0
|
2月前
|
Python 容器 人工智能
Python每日一练(20230402) 对称二叉树、全排列、盛最多水的容器
Python每日一练(20230402) 对称二叉树、全排列、盛最多水的容器
25 0
Python每日一练(20230402) 对称二叉树、全排列、盛最多水的容器
|
2月前
|
索引 容器
leetcode-6130:设计数字容器系统
leetcode-6130:设计数字容器系统
23 0
|
2月前
|
人工智能 容器
leetcode-11:盛最多水的容器
leetcode-11:盛最多水的容器
20 0
|
2月前
|
存储 算法 Java
Leetcode算法系列| 11. 盛最多水的容器
Leetcode算法系列| 11. 盛最多水的容器
|
2月前
|
算法 Java C++
【数据结构和算法】盛最多水的容器
给定一个长度为n的整数数组height。有n条垂线,第i条线的两个端点是(i, 0)和(i, height[i])。 找出其中的两条线,使得它们与x轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明:你不能倾斜容器。
20 2
【数据结构和算法】盛最多水的容器
|
3月前
|
人工智能 容器
【 腾讯精选练习 50 题】15—盛最多水的容器【中等】
【 腾讯精选练习 50 题】15—盛最多水的容器【中等】
|
13天前
|
存储 索引
《LeetCode》—— LeetCode刷题日记
《LeetCode》—— LeetCode刷题日记

相关产品

  • 容器镜像服务
  • 容器服务Kubernetes版