首页 > 编程语言 >leetcode算法热题--盛最多水的容器

leetcode算法热题--盛最多水的容器

时间:2024-05-01 11:11:34浏览次数:30  
标签:tmp 容器 -- res 复杂度 height int 最多水 热题

题目

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

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

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

说明:你不能倾斜容器。
示例 1:
图片alt

输入:[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

解答

方法一:暴力求解法
思路和算法
我们很容易就能想到,使用两个for循环将所有情况都算出来,取最大值即可。

代码
class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int tmp = 0;
        for(int i = 0;i < height.size()-1;i++)
        {
            for(int j = i + 1;j < height.size();j++)
            {
                tmp = (j - i) * min(height[j],height[i]);
                res = max(tmp,res);
            }
        }
        return res;
    }
};
复杂度分析

时间复杂度:O[n^2]。使用了两个for循环嵌套循环,每一个循环n次。
空间复杂度:O[1],只使用了有限个变量来记录数据。

方法二:双指针法
第一种方法由于时间复杂度过高,导致提交时,时间超限,没有通过,我们使用第一种方法求解时,对于容器的底长使用了一个for来计算,导致时间复杂过高。我们可以使用两个变量分别从数组的开始和结束分别向中间靠拢,这样我们就不用再去使用多余的for循环来计算底长了,我们就能将时间复杂度降低为O[n]。

代码
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size()-1;
        int res = 0;
        int tmp;
        while(left<right)
        {
            tmp = (right - left) * min(height[right],height[left]);
            res = max(tmp,res);
            if(height[right]>height[left])
                left++;
            else
                right--;
        }
        return res;
    }
};
复杂度分析

时间复杂度:O[n],双指针总计最多遍历整个数组一次。
空间复杂度:O[1],使用有限的变量来记录数据。

标签:tmp,容器,--,res,复杂度,height,int,最多水,热题
From: https://www.cnblogs.com/oyoy/p/18169100

相关文章

  • 【Qt之JSON文件】QJsonDocument、QJsonObject、QJsonArray等类介绍及使用
    简述Qt5中包含了处理JSON的类,均以QJson开头(例如:QJsonDocument、QJsonArray、QJsonObject),在QtCore模块中,不需要额外引入其它模块。简述常用的JSON库JSON常用类简单的JSON对象简单的JSON数组复杂的JSON更多参考 常用的JSON库json.org 中介绍了......
  • [MRCTF2020]套娃
    [MRCTF2020]套娃打开环境发现有张图片显示不出来查看网页源代码发现部分代码$query=$_SERVER['QUERY_STRING'];if(substr_count($query,'_')!==0||substr_count($query,'%5f')!=0){die('Y0uareSocutE!');}if($_GET['b_u_p_t�......
  • Python学习之路 第五篇 基本数据类型
    int类型:在python3里不论数有多大,永远都是int类型。在python2里整形(数字),在范围内叫int,超出范围叫long,也叫长整型。在python3里所有整形(数字)的功能都包含在int里。int功能展示:输入int摁住ctrl键然后同时将鼠标箭头放在int上出现小手后点击进去就能看到int所具有的功能。表示所有的数......
  • 记录两个BLE讲得很好的博客(以后不懂直接看)
    前言本来打算总结一下自己对BLE的理解,在啃CoreSpec的时候发现了这俩个博客,讲的深入浅出,还图文并茂。感觉自己应该也写不出来花来,还是不献丑了。参考资料iini:https://home.cnblogs.com/u/iini爱洋葱StephenZhou:https://stephenzhou.blog.csdn.net/?type=blogBluetoothS......
  • 推荐3款程序员常用的画图工具
    前言经常看到有小伙伴在DotNetGuide技术社区微信交流群里问:有什么好用的画图工具推荐的?今天大姚给大家推荐3款程序员日常工作中常用的画图工具,大家可以根据自己的需求选择。ProcessOnProcessOn是一款专业强大在线作图工具,提供AI生成思维导图流程图,支持思维导图、流程图、组织结......
  • go学习03
    路由分组 v1:=router.Group("/v1") { v1.POST("/login",loginEndpoint) v1.POST("/submit",submitEndpoint) v1.POST("/read",readEndpoint) } v2:=router.Group("/v2") { v2.POST("/login",l......
  • C. Matching Arrays
    链接:https://codeforces.com/problemset/problem/1896/C洛谷:https://www.luogu.com.cn/problem/CF1896C这题疑似有点水了?为什么还有绿题hhhh思路:结构体+排序首先对a,b各自排序:取b的下x和a的上x比较,如果可以(指ai>bi),那么进入二阶段;如果不行,那么直接输出no。二阶段:取b的上n-x和a的......
  • 《Node.js+Vue.js+MangoDB全栈开发实战》已出版
    《Node.js+Vue.js+MangoDB全栈开发实战》随书源码下载地址:链接:https://pan.baidu.com/s/1DQYgPZLmtJCIuDXs8gub_w?pwd=1127提取码:1127课件下载地址:链接:https://pan.baidu.com/s/1M36y1xu-gIUidDxw38GlBg提取码:1988随书目录目   录第1章 Node.js和TypeScript基础·......
  • C. Mixing Water
    https://codeforces.com/contest/1359/problem/C题意:给h和c两个数,并且操作顺序必须是hchchchch...对这些操作求和后除以操作次数得到均值,要求这个均值尽可能的接近t。问在最接近t的情况下,最少需要进行多少次操作。思路:如果(h+c)/2>=t,那么则只需两次操作最优。如果h==t,......
  • ' for reading (没有那个文件或目录)en file `
     001、奇怪的报错:'forreading(没有那个文件或目录)enfile`[sy20223040796@admin1test]$ls##测试文件及命令test.bedtest.sh[sy20223040796@admin1test]$cattest.bed##测试文件1540000154000021542500154250021......