当前位置: 首页 > 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…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...