首页 > 其他分享 >11. 盛最多水的容器【 力扣(LeetCode) 】

11. 盛最多水的容器【 力扣(LeetCode) 】

时间:2024-08-16 14:57:02浏览次数:13  
标签:11 容器 capacity int max height 力扣 最多水 指针

一、题目描述

给定一个长度为 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

三、解题思路

  1. 基本思路:
      双指针,从最长宽度一直收缩,记录下最大容积。
  2. 具体思路:
    • 预处理:定义头指针 i 和尾指针 j ,初始化为 0 和 n-1 。定义 max_capacity ,表示最大容量,初始化为 0 。
    • 遍历:因为刚开始是最大宽度,高度不确定,要想增大容积,只能增加高度,所以头指针和尾指针比较,小的那个进行移动,以寻找更高的高度。在寻找期间,不断比较容积,记录下最大的那个。

四、参考代码

时间复杂度: O ( n ) \Omicron(n) O(n)
空间复杂度: O ( 1 ) \Omicron(1) O(1)

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n=height.size();
        int i=0,j=n-1;
        int max_capacity=0;

        while(i<j){
            max_capacity=max((j-i)*min(height[i],height[j]),max_capacity);
            if(height[i]<height[j])
                i++;
            else
                j--;
        }

        return max_capacity;
    }
};

标签:11,容器,capacity,int,max,height,力扣,最多水,指针
From: https://blog.csdn.net/yyh520025/article/details/141224816

相关文章

  • 15. 三数之和【 力扣(LeetCode) 】
    一、题目描述给你一个整数数组nums,判断是否存在三元组[nums[i],nums[j],nums[k]]满足i!=j、i!=k且j!=k,同时还满足nums[i]+nums[j]+nums[k]==0。请你返回所有和为0且不重复的三元组。注意:答案中不可以包含重复的三元组。二、测试用例示例1:输......
  • Win 11 Postgresql 16 安装失败解决方案
    主要遇到以下两个问题一个是在安装时报错Problemrunningpost-installstep.InstallationmaynotcompletecorrectlyThedatabaseclusterinitialisationfailed.一个是在初始化时报错Theprogram"postgres"wasfoundby"initdb"butwasnotthesameversionasin......
  • 【力扣高频题】021.括号生成
    上篇文章我们学习了判断一个字符串是否是有效的括号顺序:有效的括号。今天我们继续来学习一道有关有效括号的中等难度题目。22.括号生成数字n代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合。示例1:输入:n=3输出:[“((())......
  • 力扣 | 一维简单线性dp | 2140. 解决智力问题、322. 零钱兑换、2466. 统计构造好字符
    文章目录一、2140.解决智力问题二、322.零钱兑换三、2466.统计构造好字符串的方案数四、91.解码方法五、983.最低票价六、790.多米诺和托米诺平铺需要特别注意的题目有2140.解决智力问题和983.最低票价,因为这两个题目可以启发思路,其他的题都比较普通。一、21......
  • 力扣 | 动态规划 | 状态机 | 买卖股票 | 买卖股票的最佳时机
    文章目录一、309.买卖股票的最佳时机含冷冻期二、714.买卖股票的最佳时机含手续费三、123.买卖股票的最佳时机III四、188.买卖股票的最佳时机IV本质上这种属于动态规划题目但又有多种状态的,我们只需要正确定义出状态即可。可能每个人定义的状态不一样,但只要是对......
  • (路由卷1)-11-EIGRP over WAN实验
    framerelaynbma网络没有广播多路访问网络静态map动态map帧中继拓扑结构full全互联(不建议使用)部分互联hubandspoke一个中心多个分支eigrp工作帧中继网络hello包围60sholdtime为180sfr接口1.物理接口2.点到点子接口3.多点子接口eigrpunicast邻居neighbor1.1.1......
  • 题解:P10111 [GESP202312 七级] 纸牌游戏
    题目大意给出三个序列:\(a\),\(b\),\(c\)分别表示:分数,罚分以及小杨从第\(1\)轮至第\(......
  • 力扣第五十九题——螺旋矩阵II
    内容介绍给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 nxn 正方形矩阵 matrix 。示例1:输入:n=3输出:[[1,2,3],[8,9,4],[7,6,5]]示例2:输入:n=1输出:[[1]]提示:1<=n<=20完整代码classSolution{publi......
  • 打靶记录11——Billu_b0x
    靶机:https://download.vulnhub.com/billu/Billu_b0x.zip难度:中(两种攻击路线)目标:取得root权限涉及的攻击方法:主机发现端口扫描Web信息收集SQL注入(Sqlmap跑不出来)文件包含漏洞文件上传漏洞源码审计内核漏洞提权注意:选择包含所有网卡的MAC地址,就能正常获取IP......
  • 洛谷——P1102 A-B 数对
    题目背景出题是一件痛苦的事情!相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的A+BProblem,改用A-B了哈哈!题目描述给出一串正整数数列以及一个正整数CCC,......