当前位置: 首页 > news >正文

【算法专题】双指针—盛最多水的容器

一、题目解析

 

分析这个题目不难得出一个容积公式

 

二、算法原理

解法一:暴力枚举(超时)

套用上述的容积公式,使用两个for循环来枚举出所有可能的情况,再挑出最大值即可,但是这种写法会超时,导致不通过。时间复杂度是O(n^2)

class Solution {
public:int maxArea(vector<int>& height) {int n = height.size();int ret = 0;    for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {ret = max(ret, min(height[i], height[j]) * (j - i));}}return ret;}
};

可以自己去尝试一下。 

解法二:双指针 

设两个指针left,right分别为这个容器的左边界和右边界,根据容积公式可得

v = min( height[right], height[left]) * (right - left)

从题目中的测试用例中选取一段进行分析如下:

所以我们可以得出结论用较小的数向内枚举的话容积肯定是在减小的,所以较小的数我们就可以不用向后枚举了直接跳过,用较大的数向后枚举就行。 

最后选出容积最大值就行了。 时间复杂度是O(n)。

三、代码编写

class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1, ret = 0;while(left < right){int v = min(height[left],height[right]) * (right - left);ret = max(ret, v);if(height[left] < height[right]){left++;}else {right--;}}return ret;}
};

相关文章:

【算法专题】双指针—盛最多水的容器

一、题目解析 分析这个题目不难得出一个容积公式 二、算法原理 解法一&#xff1a;暴力枚举&#xff08;超时&#xff09; 套用上述的容积公式&#xff0c;使用两个for循环来枚举出所有可能的情况&#xff0c;再挑出最大值即可&#xff0c;但是这种写法会超时&#xff0c;导致…...

java入门,程序=数据结构+算法

一、前言 在学习java的时候&#xff0c;我印象最深的一句话是&#xff1a;程序数据结构算法&#xff0c;对于写java程序来说&#xff0c;这就是java的入门。 二、java基本数据结构与算法 1、数据类型 java中的数据类型8种基本数据类型&#xff1a; 整型 byte 、short 、int…...

9.MySQL索引的操作

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 目录 索引操作 查询索引 创建主键索引 唯一索引的创建 普通索引的创建 全文索引的创建 删除索引 索引创建原则 索引操作 查询索引 第一种方法&#xff1a; show keys from 表名\G 我们了解其中几个就好。 第二种方法…...

大型加油站3d全景虚拟现实展示平台实现全方位立体呈现

近年来&#xff0c;随着国民经济的快速发展&#xff0c;交通基础设施的不断改善&#xff0c;机动车保有量的持续飙升&#xff0c;以至于加油站的建设数量和密度也在不断扩张。加油站作为人流量大且常见的城市场景&#xff0c;对加油站进行安全防范措施具有非常重要的安全意义。…...

Reading:Deep dive into the OnPush change detection strategy in Angular

原文连接&#xff1a;IndepthApp 今天深入阅读并总结Angualr中onPush更新策略。 1. 两种策略 & whats Lview&#xff1f; Angular 实现了两种策略来控制各个组件级别的更改检测行为。这些策略定义为Default和OnPush&#xff1a; 被定义为枚举&#xff1a; export enum…...

野火霸天虎 STM32F407 学习笔记_1 stm32介绍;调试方法介绍

STM32入门——基于野火 F407 霸天虎课程学习 前言 博主开始探索嵌入式以来&#xff0c;其实很早就开始玩 stm32 了。但是学了一段时间之后总是感觉还是很没有头绪&#xff0c;不知道在学什么。前前后后分别尝试了江协科技、正点原子、野火霸天虎三次 stm32 的课程学习。江协科…...

@reduxjs/toolkit配置react-redux解决createStore或将在未来被淘汰警告

通常 我们用redux都需要通过 createStore 但目前 你去用它 基本都会被划线 甚至有点厉害的的编辑器 他会直接告诉你这个东西基本快被弃用了 这个应该大家都知道 最好不要用已经被明确未来或弃用的语法 因为一旦弃用这个系统就需要维护 而且说 一般会被淘汰的语法 本身也就是有…...

致敬1024天前的自己

今早打开手机就收到了来自CSDN的消息&#xff0c;哦&#xff0c;距离我发表第一篇技术博客已经过去1024个日夜了。 我第一次发技术博客是我大二做完我第一个网站时写的。因为网站需要上线服务器&#xff0c;涉及到不少linux相关的知识&#xff0c;我在自学的过程中走了不少弯路…...

〖Python网络爬虫实战㊱〗- JavaScript 网站加密和混淆

订阅:新手可以订阅我的其他专栏。免费阶段订阅量1000+python项目实战 Python编程基础教程系列(零基础小白搬砖逆袭) 说明:本专栏持续更新中,订阅本专栏前必读关于专栏〖Python网络爬虫实战〗转为付费专栏的订阅说明作者:爱吃饼干的小白鼠。Python领域优质创作者,2022年度…...

基于单片机设计的电子柜锁

一、前言 随着现代社会的不断发展&#xff0c;电子柜锁的应用越来越广泛。传统的机械柜锁存在一些不便之处&#xff0c;例如钥匙容易丢失、密码容易泄露等问题。设计一款基于单片机的电子柜锁系统成为了一个有趣而有意义的项目。 该电子柜锁系统通过电磁锁作为柜锁的开关&…...

Windows安装tensorflow-gpu=1.14.0CUDA=10.0cuDNN=7.4 (多版本CUDA共存)

文章目录 0. 前置说明1. 查看版本对应关系2. 安装 cuda3. 安装 cudnn4. 添加环境变量5. 安装 tensorflow 0. 前置说明 本机&#xff08;Windows 11&#xff09;已安装CUDA 11.7 使用命令查看显卡驱动&#xff1a; nvidia-smi这里显示的CUDA Version: 11.7说明支持安装11.7版本…...

CodeWhisperer 初体验

文章作者&#xff1a;1颗 orange 最近用了一个叫 CodeWhisperer 的插件&#xff0c;这个软件对于来说开发人员&#xff0c;插件有好多实用的功能&#xff0c;编码更高效&#xff0c;代码质量也提升了很多。 CodeWhisperer 简介 CodeWhisperer 是亚⻢逊出品的一款基于机器学习…...

HNU-算法设计与分析-讨论课1

第一次小班讨论 &#xff08;以组为单位&#xff0c;每组一题&#xff0c;每组人人参与、合理分工&#xff0c;ppt中标记分工&#xff0c;尽量都有代码演示&#xff09; 1.算法分析题 2-10、2-15(要求&#xff1a;有ppt&#xff08;可代码演示&#xff09;) 2.算法实现题 2-4、…...

java连接zookeeper

API ZooKeeper官方提供了Java API&#xff0c;可以通过Java代码来连接zookeeper服务进行操作。可以连接、创建节点、获取节点数据、监听节点变化等操作&#xff0c;具体有以下几个重要的类&#xff1a; ZooKeeper&#xff1a;ZooKeeper类是Java API的核心类&#xff0c;用于与…...

2023-11-01 node.js-electron-环境配置-记录

摘要: 2023-11-01 node.js-electron-环境配置-记录 相关文档: Node.js Build cross-platform desktop apps with JavaScript, HTML, and CSS | Electron node.js的国内源 - Python技术站 node.js 下载地址: https://nodejs.org/dist/v20.9.0/ 说明: 最好使用最新版本当前我使…...

使用 ElementUI 组件构建 Window 桌面应用探索与实践(WinForm)

零、实现原理与应用案例设计 1、原理 基础实例 Demo 可以参照以下这篇博文&#xff0c; 基于.Net CEF 实现 Vue 等前端技术栈构建 Windows 窗体应用-CSDN博客文章浏览阅读291次。基于 .Net CEF 库&#xff0c;能够使用 Vue 等前端技术栈构建 Windows 窗体应用https://blog.c…...

使用C++构建安全队列

1 背景 STL的容器不是线程安全的&#xff0c;我们经常会有需求要求数据结构线程安全&#xff0c;比如写生产者消费者模型的时候&#xff0c;就要求队列线程安全。利用std::queue和C线程标准库的一些组件&#xff08;mutex&#xff0c;condition_variable&#xff09;&#xff…...

EasyFlash移植使用- 关于单片机 BootLoader和APP均使用的情况

目前&#xff0c;我的STM32单片机&#xff0c;需要在BootLoader和APP均移植使用EasyFlash&#xff0c;用于参数管理和IAP升级使用。 但是由于Flash和RAM限制&#xff0c;减少Flash占用&#xff0c;我规划如下&#xff1a; BootLoader中移植EasyFlash使用旧版本&#xff0c;因为…...

python捕获异常和scapy模块的利用

Python捕获异常 ​ 当程序运行时&#xff0c;因为遇到未知的错误而导致中止运行&#xff0c;便会出现Traceback 消息&#xff0c;打印异常。异常即是一个事件&#xff0c;该事件会在程序执行过程中发生&#xff0c;影响程序的正常执行。一般情况下&#xff0c;在Python 无法正…...

CSS+Javascript+Html日历控件

最近&#xff0c;因需要用HTMLJAVASCRIPTCSS实现了一个日历控件&#xff0c;效果如下&#xff1a; 单击上月、下月进行日历切换。当前日期在日历中变颜色标注显示。还是老老套路、老方法&#xff0c;分HMLCSSJAVASCRIPT三部分代码。 一、html代码 <h1>学习计划</h1…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...