【刷题之路Ⅱ】LeetCode 11.盛水最多的容器

【刷题之路Ⅱ】LeetCode 11.盛水最多的容器

  • 一、题目描述
  • 二、解题
    • 1、方法1——暴力法
      • 1.1、思路分析
      • 1.2、代码实现
    • 2、方法2——双指针
      • 2.1、思路分析
      • 2.2、代码实现

一、题目描述

原题连接: 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

二、解题

1、方法1——暴力法

1.1、思路分析

用两层for循环枚举出所有的垂线组合,而我们知道能成多少水一定是由垂线中较短的那一条来决定的:
在这里插入图片描述
所以我们每一次枚举都要找到较短的那一条short_plank,用short_plank乘上两条垂线之间的距离就得出这两条垂线所形成的容器的容量了。
当我们枚举完所有的组合,我们也就求出了最大的盛水量。

1.2、代码实现

有了以上思路,那我们写起代码来也就水到渠成了:

int maxArea1(int* height, int heightSize) {
	assert(height);
	int i = 0;
	int j = 0;
	int max_area = 0; // 保存最大的容器容量
	for (i = 0; i < heightSize - 1; i++) {
		for (j = i + 1; j < heightSize; j++) {
			int short_plank = 0; // 每次枚举到的容器的短板
			int area = 0; // 每次枚举到的容器的容量
			short_plank = height[i] < height[j] ? height[i] : height[j];
			area = short_plank * (j - i);
			if (area > max_area) {
				max_area = area;
			}
		}
	}
	return max_area;
}

时间复杂度:O(n^2),其中n为数组元素个数。
空间复杂度:O(1),我们只需要用到常数级的额外空间。

但这个程序的时间复杂度太高了,提交给LeetCode是不给通过的。

2、方法2——双指针

2.1、思路分析

既然题目要我们找到两块“木板”,那我们很容易就想到要使用双指针
我们可以先让两个指针left和right指向序列的两端:
在这里插入图片描述
因为容器的可容水容量由left和right中更短的那一条决定,所以我们每次只需要移动更短的那条:
在这里插入图片描述
并判断移动后容器是否增容,如果height[left] 和 height[left + 1]相同或者height[right] 和 height[right - 1]相同:
在这里插入图片描述
说明下次移动后的容器容量只能是减小的,所以跳过height[left + 1]或height[right - 1]直接判断height[left + 2] 或height[right - 2]:
在这里插入图片描述

2.2、代码实现

有了以上思路,那我们写起代码来也就水到渠成了:

int maxArea2(int* height, int heightSize) {
	assert(height);
	int max_area = 0; // 存储最大的盛水容量
	int left = 0;
	int right = heightSize - 1;
	int area = 0;
	int short_plank = 0;
	while (left < right) {
		short_plank = height[left] < height[right] ? height[left] : height[right];
		area = short_plank * (right - left);
		if (area > max_area) {
			max_area = area;
		}
		if (height[left] <= height[right]) {
			if (height[left] == height[left + 1]) {
				left += 2;
			}
			else {
				left++;
			}
		}
		else {
			if (height[right] == height[right - 1]) {
				right -= 2;
			}
			else {
				right--;
			}
		}
	}
	return max_area;
}

时间复杂度:O(n),其中n为数组元素个数,我们只需要遍历一遍数组及可。
空间复杂度:O(1),我们只需要用到常数级的额外空间。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/1115.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

44岁了,我从没想过在CSDN创作2年,会有这么大收获

1998年上的大学&#xff0c;02年毕业&#xff0c;就算从工作算起&#xff0c;我也有20余年的码龄生涯了。 但正式开启博文的写作&#xff0c;却是2021年开始的&#xff0c;差不多也就写了2年的博客&#xff0c;今天我来说说我在CSDN的感受和收获。 我是真的没想到&#xff0c;…

QT串口助手开发3串口开发

系列文章目录 QT串口助手开发3串口开发 QT串口助手开发3系列文章目录一、UI界面程序的编写二、发送框程序编写一、UI界面程序的编写 根据上文的未解决问题&#xff1a;我们打开串口按钮打开后只能选择关闭串口&#xff0c;所以这个是循环的过程 上文链接 所以按钮对应的槽函数…

【C++】搜索二叉树(保姆教程)

&#x1f345;二叉树底层是堆&#xff0c;之前学习的简单二叉树不是大堆就是小堆&#xff0c;今天是二叉树进阶&#xff0c;一定要好好掌握&#xff01; 目录 ☃️1.搜索二叉树介绍 ☃️2.底层实现 ☃️3.key模型和key&#xff0c;value模型 ☃️1.搜索二叉树介绍 右>根&…

蜻蜓优化算法Python代码(详细注释)

1.代入例子&#xff0c;目标函数求最优解迭代过程&#xff1a;蜻蜓算法流程&#xff1a;蜻蜓算法&#xff08;Dragonfly Algorithm&#xff09;是一种基于种群的优化算法&#xff0c;灵感来自于蜻蜓的群集行为。该算法通过模拟蜻蜓之间的吸引力和斥力&#xff0c;以及蜻蜓的移动…

IDEA好用插件:MybatisX快速生成接口实体类mapper.xml映射文件

目录 1、在Idea中找到下载插件&#xff0c;Install&#xff0c;重启Idea 2、一个测试java文件&#xff0c;里面有com包 3、在Idea中添加数据库 --------以Oracle数据库为例 4、快速生成entity-service-mapper方法 5、查看生成的代码 6、自动生成&#xff08;增删查改&#xff0…

C++ | 对比inline内联函数和宏的不同点

文章目录一、前言二、宏的优缺点分析1、概念回顾2、宏的缺点3、宏的优点三、inline内联函数1、概念2、特性①&#xff1a;空间换时间&#x1f381;趣味杂谈&#xff1a;庞大的游戏更新包3、特性②&#xff1a;inline实现机制4、特性③&#xff1a;inline的声明与定义反汇编观察…

【链表OJ题(八)】相交链表

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录链表OJ题(八)8. 相交…

【C++笔试强训】第三十二天

&#x1f387;C笔试强训 博客主页&#xff1a;一起去看日落吗分享博主的C刷题日常&#xff0c;大家一起学习博主的能力有限&#xff0c;出现错误希望大家不吝赐教分享给大家一句我很喜欢的话&#xff1a;夜色难免微凉&#xff0c;前方必有曙光 &#x1f31e;。 &#x1f4a6;&a…

Spring Bean实例化和初始化的过程

承接上文Spring Bean生命周期应用程序在运行过程中能否去读取当前系统的环境变量或系统属性?这里涉及到一个非常重要的接口Environment&#xff0c;System.getenv&#xff0c;System.getProperties都是获取当前系统环境变量&#xff0c;Environment接口的实现类AbstractEnviro…

浏览器前进与后退的秘密——栈 (栈的理解与实现)

文章目录前言&#xff1a;浏览器与栈的纠缠如何理解“栈”&#xff1f;如何实现一个“栈”&#xff1f;基于数组的顺序栈基于链表的链式栈解答开篇&#x1f431;‍&#x1f409;作者简介&#xff1a;大家好&#xff0c;我是黑洞晓威&#xff0c;一名大二学生&#xff0c;希望和…

每日算法题

题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 作为篮球队教练&#xff0c;你需要从以下名单中选出 11 号位至 55 号位各一名球员&#xff0c;组成球队的首发阵容。 每位球员担任 11 号位至 55 号位时的评分如下…

CCF-CSP真题《202212-3 JPEG 解码》思路+python,c++满分题解

想查看其他题的真题及题解的同学可以前往查看&#xff1a;CCF-CSP真题附题解大全 试题编号&#xff1a;202212-3试题名称&#xff1a;JPEG 解码时间限制&#xff1a;1.0s内存限制&#xff1a;512.0MB问题描述&#xff1a; 问题背景 四年一度的世界杯即将画上尾声。在本…

STM32 OTA应用开发——通过串口/RS485实现OTA升级(方式2)

STM32 OTA应用开发——通过串口/RS485实现OTA升级&#xff08;方式2&#xff09; 目录STM32 OTA应用开发——通过串口/RS485实现OTA升级&#xff08;方式2&#xff09;前言1 环境搭建2 功能描述3 程序编写3.1 BootLoader部分3.2 APP的制作4 修改工程中的内存配置4.1 Bootloader…

面试阿里测开岗失败后,被面试官在朋友圈吐槽了......

前一阵子有个徒弟向我诉苦&#xff0c;说自己在参加某大厂测试面试的时候被面试官怼得哑口无言&#xff0c;场面让他一度十分尴尬印象最深的就是下面几个问题&#xff1a;根据你以前的工作经验和学习到的测试技术&#xff0c;说说你对质量保证的理解&#xff1f;非关系型数据库…

HashMap扩容为什么每次都是之前的2倍

一. 背景介绍HashMap的底层是通过数组链表红黑树的数据结构来存放数据的。我们知道&#xff0c;当新添加元素的key值出现了hash碰撞&#xff0c;就会在同一个bucket中形成链表或者红黑树。当键值对的数量超过阈值时就会扩容&#xff0c;将以前处于同一个链表或者红黑树上的元素…

持续集成 在 Linux 上搭建 Jenkins,自动构建接口测试

本篇把从 0 开始搭建 Jenkins 的过程分享给大家&#xff0c;希望对小伙伴们有所帮助。 文章目录 在 Linux 上安装 Jenkins在 Linux 上安装 Git在 Linux 上安装 Python在 Linux 上安装 Allure配置 Jenkinsjenkins 赋能 - 使用邮箱发送测试报告jenkins 赋能 - 优化测试报告内容…

C语言刷题(6)(猜名次)——“C”

各位CSDN的uu们你们好呀&#xff0c;今天&#xff0c;小雅兰还是在复习噢&#xff0c;今天来给大家介绍一个有意思的题目 题目名称&#xff1a; 猜名次 题目内容&#xff1a; 5位运动员参加了10米台跳水比赛&#xff0c;有人让他们预测比赛结果&#xff1a; A选…

测试管理之路 —— 如何优化测试计划以提高测试覆盖率

&#x1f60f;作者简介&#xff1a;博主是一位测试管理者&#xff0c;同时也是一名对外企业兼职讲师。 &#x1f4e1;主页地址&#xff1a;&#x1f30e;【Austin_zhai】&#x1f30f; &#x1f646;目的与景愿&#xff1a;旨在于能帮助更多的测试行业人员提升软硬技能&#xf…

Github的使用

Github Date: March 8, 2023 Sum: Github的使用 Github 了解开源相关的概念 1. 什么是开源 2. 什么是开源许可协议 开源并不意味着完全没有限制&#xff0c;为了限制使用者的使用范围和保护作者的权利&#xff0c;每个开源项目都应该遵守开源许可协议&#xff08; Open Sou…

node多版本控制

前言 最近在折腾Python&#xff0c;并将node升级至v18.14.2。突然发现一个旧项目无法运行&#xff0c;也无法打包&#xff0c;里面的node-sass报错&#xff0c;显然这是因为node版本过高导致的。 将node版本降低至以前的v14.16.0&#xff0c;果然立马就能正常运行。 存在不同…
最新文章