每日一练【盛最多水的容器】

一、题目描述

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

二、题目解析

这题如果使用暴力枚举,会发现leetcode上显示超时,我们学习算法,目的就是掌握更多优秀的算法,所以暴力枚举直接摒弃掉。下面讲解时间复杂度为O(N)的双指针优秀算法:
我们首先明确一个规律:

以示例一为例,我们直接定义数组最左边为左值,数组的最右边为右值,最左边是1,保持最左边不动,然后移动最右边,会发现任何一个面积都比之前最右边的小,因为面积是由长度和高决定的,但高度不变或者变小,同样变化的还有长度,长度一定是变小的,所以左值直接摒弃。

总体思路就是先找两边高度的小值,并计算当前最大值然后摒弃最小值,缩小数组范围,继续遍历,直到left和right指针相遇,因此该算法的时间复杂度就是O(N)

三、原码

int maxArea(int* height, int heightSize) {//还是利用快慢指针的算法    int left = 0;int right = heightSize - 1;int minh = 0;int maxArea_ = 0;while(left < right){int flag = 0;//在循环体里的变量尽量都要在循环里面重定义!!!if(height[left] <= height[right]){minh = height[left];flag = -1;}elseminh = height[right];int Area = minh * (right - left);if(maxArea_ < Area)maxArea_ = Area;if(flag == 0)right--;elseleft++;}return maxArea_;
}

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

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

相关文章

Qt Creator使用Heob检测内存泄漏

开发环境&#xff1a;win10 qt5.12.0 编译环境:MinGW 使用内存泄漏排查工具heob步骤如下: 第一步:下载heob.exe--注&#xff1a;我本机仅有heob.exe还不行&#xff0c;提示如下 所以需要下载heob和Dwarfstack&#xff0c;然后把他们放到同级目录下&#xff0c;我已经下载并且…

Mybatis中的设计模式

Mybatis中的设计模式 Mybatis中使用了大量的设计模式。 以下列举一些看源码时&#xff0c;觉得还不错的用法&#xff1a; 创建型模式 工厂方法模式 DataSourceFactory 通过不同的子类工厂&#xff0c;实例化不同的DataSource TransactionFactory 通过不同的工厂&#xff…

js moment时间范围拿到中间间隔时间

2023.11.27今天我学习了如何对只返回的开始时间和结束时间做处理&#xff0c;比如后端返回了&#xff1a; [time:{start:202301,end:202311}] 我们需要把中间的间隔渲染出来。 [202301,202302,202303,202304,202305,202306,202307,202308,202309,202310,202311] 利用moment…

01 高等数学.武忠祥.0基础

第一章 函数与极限 01映射与函数 02 函数概念 对应法则 定义域 常见函数 函数的几种特性 周期函数不一定有最小周期。 涉及额外与复习 存在与任意的关系

Star 10.4k!推荐一款国产跨平台、轻量级的文本编辑器,内置代码对比功能

notepad 相信大家从学习这一行就开始用了&#xff0c;它是开发者/互联网行业的上班族使用率最高的一款轻量级文本编辑器。但是它只能在Windows上进行使用&#xff0c;而且正常来说是收费的&#xff08;虽然用的是pj的&#xff09;。 对于想在MacOS、Linux上想使用&#xff0c;…

关于使用百度开发者平台处理语音朗读问题排查

错误信息&#xff1a;"convert_offline": false, "err_detail": "16: Open api characters limit reach 需要领取完 识别和合成都要有

Clean 架构下的现代 Android 架构指南

Clean 架构下的现代 Android 架构指南 Clean 架构是 Uncle Bob 提出的一种软件架构&#xff0c;Bob 大叔同时也是 SOLID 原则的命名者。 Clean 架构图如下&#xff1a; 这张图描述的是整个软件系统的架构&#xff0c;而不是单体软件&#xff0c;其中至少包括服务端以及客户端…

【Java】类和对象之超级详细的总结!!!

文章目录 前言1. 什么是面向对象&#xff1f;1.2面向过程和面向对象 2.类的定义和使用2.1什么是类&#xff1f;2.2类的定义格式2.3类的实例化2.3.1什么是实例化2.3.2类和对象的说明 3.this引用3.1为什么会有this3.2this的含义与性质3.3this的特性 4.构造方法4.1构造方法的概念4…

ElasticSearch学习笔记(一)

计算机软件的学习&#xff0c;最重要的是举一反三&#xff0c;只要大胆尝试&#xff0c;认真验证自己的想法就能收到事办功倍的效果。在开始之前可以看看别人的教程做个快速的入门&#xff0c;然后去官方网站看看官方的教程&#xff0c;有中文教程固然是好&#xff0c;没有中文…

dcat admin日志扩展 dcat-log-viewer 遇到的问题记录

扩展地址&#xff1a; https://github.com/duolabmeng6/dcat-log-viewer 问题描述&#xff1a; 使用很简单&#xff0c;直接安装扩展包&#xff0c;开启扩展就可以了&#xff0c;会自动生成菜单。 之前在别的系统用过&#xff0c;没问题&#xff0c;今天在一个新的系统用的时…

【网络奇缘】- 计算机网络|分层结构|深入探索TCP/IP模型|5层参考模型

​ &#x1f308;个人主页: Aileen_0v0&#x1f525;系列专栏: 一见倾心,再见倾城 --- 计算机网络~&#x1f4ab;个人格言:"没有罗马,那就自己创造罗马~" 目录 OSI参考模型与TCP/IP参考模型相同点 OSI参考模型与TCP/IP参考模型不同点 面向连接三阶段&#xff08…

单片机系统

我们来看单片机 的例子&#xff0c;读者可能会担心单片机&#xff08;又称MCU&#xff0c;或微控制器&#xff09; 过于专业而无法理解。完全没必要&#xff01;在这里我们仅借它谈论一下有关时间的话题&#xff0c;顺带提一下单片机系统的概念。 单片机顾名思义是集成到一个芯…

基于SSM框架的网上书店系统

基于SSM框架的网上书店系统 文章目录 基于SSM框架的网上书店系统 一.引言二.系统设计三.技术架构四.功能实现五.界面展示六.源码获取 一.引言 随着互联网的普及和电子商务的快速发展&#xff0c;网上书店系统成为了现代人购买图书的主要方式之一。网上书店系统不仅提供了便捷的…

Redis队列stream,Redis多线程详解

Redis 目前最新版本为 Redis-6.2.6 &#xff0c;会以 CentOS7 下 Redis-6.2.4 版本进行讲解。 下载地址&#xff1a; https://redis.io/download 安装运行 Redis 很简单&#xff0c;在 Linux 下执行上面的 4 条命令即可 &#xff0c;同时前面的 课程已经有完整的视…

【UGUI】实现背包的常用操作

1. 添加物品 首先&#xff0c;你需要一个包含物品信息的类&#xff0c;比如 InventoryItem&#xff1a; using UnityEngine;[CreateAssetMenu(fileName "NewInventoryItem", menuName "Inventory/Item")] public class InventoryItem : ScriptableObje…

Postman:专业API测试工具,提升Mac用户体验

如果你是一名开发人员或测试工程师&#xff0c;那么你一定知道Postman。这是一个广泛使用的API测试工具&#xff0c;适用于Windows、Mac和Linux系统。今天&#xff0c;我们要重点介绍Postman的Mac版本&#xff0c;以及为什么它是你进行API测试的理想选择。 一、强大的功能和易…

第3章 表、栈和队列

3.4 队列ADT 像栈一样&#xff0c;队列(queue)也是表。然而&#xff0c;使用队列时插入在一端进行而删除则在另一端 进行。 3.4.1 队列模型 队列的基本操作是Enqueue(入队)一它是在表的末端(叫作队尾(rear))插入一个元素&#xff0c;还有Dequeue(出队)——它是删除(或返回)在…

前端组件库开发

通常我们会使用很多组件库&#xff0c;有时候我们会去看源码比如element&#xff0c;antd&#xff0c;然后发现多少是按需导出&#xff0c;和vue.use全局注册&#xff0c;依赖于框架的拓展。 组件库的开发依赖框架的版本和node的版本&#xff0c;这个是需要说明的&#xff0c;然…

探索人工智能领域——每日20个名词详解【day6】

目录 前言 正文 总结 &#x1f308;嗨&#xff01;我是Filotimo__&#x1f308;。很高兴与大家相识&#xff0c;希望我的博客能对你有所帮助。 &#x1f4a1;本文由Filotimo__✍️原创&#xff0c;首发于CSDN&#x1f4da;。 &#x1f4e3;如需转载&#xff0c;请事先与我联系以…

CloudCompare简单开发

一、概述 CloudCompare如何进行二次开发&#xff1f;_cloudcompare 二次开发-CSDN博客 开发一个功能&#xff0c;在原始CC的基础上添加一个拓展功能&#xff0c;如下&#xff1a; 二、功能开发 1、修改MainWindow.UI 重点是&#xff1a;要编译&#xff0c;不然在mainwindow.…