盛⽔最多的容器【双指针】

在这里插入图片描述
在这里插入图片描述

首先我们设该容器的两边为左右两边界。
这道题中的:盛⽔最大容量 = 底 * 高 = 左右两边界距离 * 左右两边界的较短板。
这道题如果用暴力求解,是个人都能想到怎么做,遍历所有的情况即可。
有没有更好的办法呢?我是搜了资料了解的。我觉得一般人【有可能只是我的知识水平太低才有这样的看法】第一次做想不出来这种情况,我们只能通过这道题的更优的思想在日后做题中可以借鉴。

那么这道题的更优法是什么呢?

首先一个容器肯定是有两边界和底边组成的,这道题的核心就是我们要找到底边*高度的最大值。
我们先把最左和最右作为容器的边界记录此时的容量,然后把左右边界的短板向相反方向移动,记录。继续移动短板知道左右指针相遇结束,取这些值的最大值作为结果。

怎么理解?

暴力求解是遍历所有的可能取最大值,这种做法其实就是依据给出的条件结合当下能利用的数据尽量的选择了一些尽可能大的值,取最大值作为结果。

为什么移动短板?

初识左右指针为最左和最右,此时我们移动其中一个,移动高的还是低的?只要移动一边,底肯定变小,如果还是移动高的一边,不仅底小了,高也小了,如果移动地的一边,虽然底小了,但是高大了,即若向内移动短板,下个水槽的面积可能增大 。若向内移动长板,下个水槽的面积一定变小。

他是如何保证舍去的值不是较大值呢?

向内移动短板(假设该短板的下标为x,此时右边界的下标为y),实际上是舍去了将x作为左边界到y-1的集合,即暴力求解是n边取2边的所有取值的集合,这个解法是每一步舍去不会作为较大值的集合。如何保证舍去的值不是较大值呢?即如何保证将x作为左边界到y-1的集合不是较大值?这些集合分别是【x, y-1】【x, y-2】… 【x, x+1】这些集合中所有取值的底边都比已经作为较大值的【x, y】的底边小,所有的高度都比已经作为较大值的【x, y】的高度小或者等于。为什么?假设这些集合中的某一个右边比x大,由于容器容量取决于短板,故高度取x;假设这些集合中的某一个右边比x小,由于容器容量取决于短板,故高度取这个右边;底边小且高度小于等于 ⇒ 舍去的都不是较大值,即舍去的可以放心舍去。

代码

class Solution
{
public:int maxArea(vector<int> &height){int left = 0, right = height.size() - 1, ret = 0;while (left < right){int volume = min(height[left], height[right]) * (right - left);ret = max(ret, volume);// 移动短板if (height[left] < height[right])left++;elseright--;}return ret;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Covalent Network(CQT)的以太坊时光机:在 Rollup 时代确保长期数据可用性

以太坊正在经历一场向 “Rollup 时代” 的转型之旅&#xff0c;这一转型由以太坊改进提案 EIP-4844 推动。这标志着区块链技术的一个关键转折&#xff0c;采用了一种被称为“数据块&#xff08;blobs&#xff09;”的新型数据结构。为了与以太坊的扩容努力保持一致&#xff0c;…

MATLAB 自定义生成平面点云(可指定方向,添加噪声)(48)

MATLAB 自定义生成平面点云(可指定方向,添加噪声)(48) 一、算法介绍二、算法步骤三、算法实现1.代码2.效果一、算法介绍 通过这里的平面生成方法,可以生成模拟平面的点云数据,并可以人为设置平面方向,平面大小,并添加噪声来探索不同类型的平面数据。这种方法可以用于…

mysql刨根问底

索引&#xff1a;排好序的数据结构 二叉树&#xff1a; 红黑树 hash表&#xff1a; b-tree&#xff1a; 叶子相同深度&#xff0c;叶节点指针空&#xff0c;索引元素不重复&#xff0c;从左到右递增排序 节点带data btree&#xff1a; 非叶子节点只存储索引&#xff0c;可…

Java_15 删除排序数组中的重复项

删除排序数组中的重复项 给你一个 非严格递增排列 的数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次 &#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的…

影视作品一键转成动漫,自媒体作者用DomoAI赢麻了

前言 众所周知&#xff0c;在自媒体爆火的那段时间&#xff0c;影视号是最容易起量的&#xff0c;借助高质量的影视&#xff0c;进行剪辑&#xff0c;解说&#xff0c;等二次创作&#xff0c;最终制作成高质量的作品&#xff0c;但是随着自媒体的发展&#xff0c;影视号越来越…

MyBatis是纸老虎吗?(七)

在上篇文章中&#xff0c;我们对照手动编写jdbc的开发流程&#xff0c;对MyBatis进行了梳理。通过这次梳理我们发现了一些之前文章中从未见过的新知识&#xff0c;譬如BoundSql等。本节我想继续MyBatis这个主题&#xff0c;并探索一下MyBatis中的缓存机制。在正式开始梳理前&am…

基于SpringBoot+MyBatis框架的智慧生活商城系统的设计与实现(源码+LW+部署+讲解)

目录 前言 需求分析 可行性分析 技术实现 后端框架&#xff1a;Spring Boot 持久层框架&#xff1a;MyBatis 前端框架&#xff1a;Vue.js 数据库&#xff1a;MySQL 功能介绍 前台功能拓展 商品详情单管理 个人中心 秒杀活动 推荐系统 评论与评分系统 后台功能拓…

测试小白必看:自动化测试入门基础知识

一、首先&#xff0c;什么是自动化测试&#xff1f; 自动化测试是把以人为驱动的测试行为转化为机器执行的一种过程。通常&#xff0c;在设计了测试用例并通过评审之后&#xff0c;由测试人员根据测试用例中描述的规程一步步执行测试&#xff0c;得到实际结果与期望结果的比较…

Vuex状态、数据持久化(vue2、vue3状态数据持久化)

简介&#xff1a;Vuex是一个仓库&#xff0c;是vue的状态管理工具&#xff0c;存放公共数据&#xff0c;任何组件都可以使用vuex里的公共数据。Vuex提供了插件系统&#xff0c;允许我们使用 vuex-persistedstate插件&#xff0c;将Vuex的状态持久化到本地存储中&#xff0c;解决…

【工具篇】总结比较几种绘画软件的优缺点

目录 一、Visio二、Processon三、draw.io四、亿图图示五、wps 写在文章开头&#xff0c;感谢你的支持与关注&#xff01;小卓的主页 一、Visio Visio 是微软公司开发的一款流程图和图表绘制软件。我们可以用它来创建各种类型的图表&#xff0c;如流程图、组织结构图、网络图、平…

【python从入门到精通】-- 第二战:注释和有关量的解释

&#x1f308; 个人主页&#xff1a;白子寰 &#x1f525; 分类专栏&#xff1a;python从入门到精通&#xff0c;魔法指针&#xff0c;进阶C&#xff0c;C语言&#xff0c;C语言题集&#xff0c;C语言实现游戏&#x1f448; 希望得到您的订阅和支持~ &#x1f4a1; 坚持创作博文…

java的一些内部小知识,类与对象的关系

目录 1. java2. 类与对象的关系 1. java test.java ---- javac --> Test.class ---- java-----> 内存 ----> cpu 源文件 二进制代码 所有正在运行的软件都在内存中有自己的内存空间 jvm —>运行java程序的&#xff0c;java虚拟机 main(); // 内部调用run()run(i…

Fiddler抓包工具之fiddler的常用快捷键

一、常用三个快捷键 ctrlX :清空所有记录 CtrlF&#xff1a;查找 F12&#xff1a;启动或者停止抓包 使用 QuickExec Fiddler2 成了网页调试必备的工具&#xff0c;抓包看数据。Fiddler2自带命令行控制。 fiddler 命令行快捷键&#xff1a;ctrl q &#xff0c;然后 输入 help…

QTday5

头&#xff1a; #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QTimerEvent> //定时器事件 #include <QTime> //时间类 #include <QtTextToSpeech> //文本转语音类 #include <QMouseEvent> //鼠标事件类 QT_BEGIN_NAMESPACE …

Redis锁,乐观锁与悲观锁

锁 悲观锁 认为什么时候都会出问题&#xff0c;无论做什么都会加锁 乐观锁 很乐观&#xff0c;认为什么时候都不会出问题&#xff0c;所以不会上锁。 更新数据时去判断一下&#xff0c;在此期间&#xff0c;是否有人修改过这个数据 应用于&#xff1a;秒杀场景 **watch*…

【保姆级讲解Edge兼容性问题解决方法】

&#x1f308;个人主页:程序员不想敲代码啊&#x1f308; &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家&#x1f3c6; &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d; 希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提…

新人应该从哪几个方面掌握大数据测试?

什么是大数据 大数据是指无法在一定时间范围内用传统的计算机技术进行处理的海量数据集。 对于大数据的测试则需要不同的工具、技术、框架来进行处理。 大数据的体量大、多样化和高速处理所涉及的数据生成、存储、检索和分析使得大数据工程师需要掌握极其高的技术功底。 需要你…

【Java程序设计】【C00366】基于(JavaWeb)Springboot的纹理生产图片系统(有论文)

TOC 博主介绍&#xff1a;java高级开发&#xff0c;从事互联网行业六年&#xff0c;已经做了六年的毕业设计程序开发&#xff0c;开发过上千套毕业设计程序&#xff0c;博客中有上百套程序可供参考&#xff0c;欢迎共同交流学习。 项目简介 项目获取 &#x1f345;文末点击卡片…

MySQL 经典练习 50 题 (记录)

前言&#xff1a; 记录一下sql学习&#xff0c;仅供参考基本都对了&#xff0c;不排除有些我做的太快做错了。里面sql不存在任何sql优化操作&#xff0c;只以完成最后输出结果为目的&#xff0c;包含我做题过程和思路最后一行才是结果。 1.过程: 1.1.插入数据 /* SQLyog Ul…

STM32之HAL开发——手动移植HAL库

HAL库移植步骤 创建目录 配置启动文件 在\Drivers\CMSIS\Device\ST\stm32f1xx\Source\Templates\ARM目录下&#xff0c;根据你的芯片型号选择对应的启动文件&#xff0c;不同容量大小的芯片&#xff0c;对应的启动文件也不一样。 注意&#xff1a;在HAL库中&#xff0c;不同容…