使用双指针法解决最大容积问题:移动较短的线以优化面积【双指针】

在解决算法问题时,我们常常需要寻找最佳的方法来提高效率。今天,我们将讨论一个经典的问题——在一组垂直线中找到两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。这篇文章将详细解析如何使用双指针法来解决这个问题,特别强调 移动较短的线 是关键。

问题描述

给定一个长度为 n 的整数数组 height,每个元素代表垂直线的高度。我们需要找到两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水,并返回这个容器的最大水量。

示例:
在这里插入图片描述

输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49

11. 盛最多水的容器 - 力扣(LeetCode)

思考过程

1. 面积计算

要计算两条线之间的面积,我们需要知道两条线之间的距离和较短的那条线的高度。设两条线的位置分别为 ij,那么它们之间的面积为:

面积 = min ⁡ ( height [ i ] , height [ j ] ) × ( j − i ) \text{面积} = \min(\text{height}[i], \text{height}[j]) \times (j - i) 面积=min(height[i],height[j])×(ji)

其中,min(height[i], height[j]) 是较短的那条线的高度,j - i 是两条线之间的距离。

2. 暴力解法(不推荐)

一个直观的解法是使用两层循环,遍历所有可能的线对,计算每对线之间的面积,并记录最大值。这种方法的时间复杂度是 O ( n 2 ) O(n^2) O(n2),对于较大的输入数组,效率非常低。

3. 双指针法(推荐)

为了提高效率,我们可以使用双指针法。这个方法的核心思想是:移动较短的那条线对应的指针,因为较短的线限制了容积,我们希望通过移动它来找到更高的线,从而可能增加面积。

解决方案

  1. 初始化两个指针,一个指向数组的开头(left),一个指向数组的末尾(right)。
  2. 计算当前指针指向的两条线之间的面积,并记录最大值。
  3. 移动较短的那条线对应的指针,因为较短的线限制了容积,我们希望通过移动它来找到更高的线,从而可能增加面积。
  4. 重复步骤 2 和 3,直到两个指针相遇。

代码实现

class Solution {
public:int maxArea(vector<int>& height) {int left = 0; // 左指针int right = height.size() - 1; // 右指针int max_area = 0; // 最大面积// 当左右指针未相遇时while (left < right) {// 计算当前面积int width = right - left;int current_height = min(height[left], height[right]);int current_area = width * current_height;max_area = max(max_area, current_area);// 移动较短的那条线对应的指针if (height[left] < height[right]) {left++; // 移动左指针} else {right--; // 移动右指针}}return max_area; // 返回最大面积}
};

详细步骤解析

  1. 初始化指针和变量

    • left 指向数组的开头,right 指向数组的末尾。
    • max_area 用于记录最大面积。
  2. 双指针迭代

    • left < right 的前提下,计算当前指针指向的两条线之间的面积:
      int width = right - left;
      int current_height = min(height[left], height[right]);
      int current_area = width * current_height;
      max_area = max(max_area, current_area);
      
    • 为什么要移动较短的线?
      • 如果我们移动较短的线,可能会找到一条更高的线 ,从而增加面积。相反,如果我们移动较长的线,由于较短的线依然限制了高度 ,面积不会增加。因此,我们总是移动较短的那条线,以期望找到更高的线来增加容积。
      if (height[left] < height[right]) {left++;
      } else {right--;
      }
      
  3. 返回结果

    • 当两个指针相遇时,迭代结束,返回 max_area 即可。

总结

通过双指针法,我们能够在 O(n) 时间复杂度内解决这个问题。该方法利用双指针逐步缩小搜索范围,并不断计算和比较面积,最终找到最大的容积。移动较短的线是解决问题的关键,因为较短的线限制了容积,我们希望通过移动它来找到更高的线,从而可能增加面积。这种方法既高效又易于理解,适用于大多数需要计算最大值或最小值的问题。

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

仪器校准中,标准样品要怎么选用?需要注意什么?

正确使用标准物质和标准样品是保证仪器校准值准确可靠的重要手段。标准物质的正确使用包括正确选择、正确使用&#xff08;防止误用&#xff09;和使用中的注意事项。 1. 参考资料证书之中给出的“参考资料的使用”信息&#xff0c;用户应予以注意。当参比材料用于证书所述用途…

自研点直播转码核心

1. 背景 视频转码是将视频文件经过解封装、解码、滤镜处理、编码、封装从而转换为另一个视频文件的过程&#xff0c;B站每天都有大量的视频原片上传后经过转码系统转换为多个不同分辨率。转换后的视频在画质接近原片的前提下会拥有更低的码率&#xff0c;因此会提高网络传输时的…

未来的智能农业:智能合约如何提升农业生产效率和可持续性

随着全球人口的增长和资源的有限性&#xff0c;农业生产面临着越来越大的挑战。如何在提高生产效率的同时保障可持续发展成为全球农业发展的关键问题。智能合约作为一种基于区块链技术的自动化执行合约&#xff0c;正在逐渐应用于农业领域&#xff0c;为农业生产带来了新的机遇…

Leetcode刷题-----移动零283复写零问题1089

目录 1.问题介绍 1.1题目要求 1.2思路分析 1.3想法实现 2.复写零问题 2.1问题分析 2.2思路分析 2.3想法实现 1.问题介绍 1.1题目要求 把这个数组里面为0的元素挪动到这个数组的后面&#xff0c;其他的非零元素的相对位置保持不变&#xff1b; 1.2思路分析 这个里面&a…

甄选范文“论软件测试中缺陷管理及其应用”软考高级论文,系统架构设计师论文

论文真题 软件缺陷指的是计算机软件或程序中存在的某种破坏正常运行能力的问题、错误,或者隐藏的功能缺陷。缺陷的存在会导致软件产品在某种程度上不能满足用户的需要。在目前的软件开发过程中,缺陷是不可避免的。软件测试是发现缺陷的主要手段,其核心目标就是尽可能多地找…

场外期权如何报价?名义本金是什么?

今天带你了解场外期权如何报价&#xff1f;名义本金是什么&#xff1f;投资者首先需要挑选自己想要进行期权交易的沪深上市公司股票。选出股票后&#xff0c;需要将股票信息、预期的操作时间&#xff08;如期限&#xff09;、看涨或看跌的选择以及预计的交易金额等信息报给场外…

Cisco OSPF LSA 类型详解指南

注&#xff1a;机翻&#xff0c;未校对。 OSPF LSA Types: The Ultimate Guide OSPF LSA Types – OSPF LSA 类型 – OSPF uses LSAs or Link state Advertisements to share information of each network and populate the LSDB (Link State Database). The LSAs are used by…

ppt模板如何制作?5个工具让你事半功倍

让我瞧瞧是谁还在为寻找PPT模板而发愁&#xff1f; 其实这可不是什么难题~身为职场高效打工人的我&#xff0c;今天便特地为大家整理了5大ppt模板ai生成神器~想知道都有哪些选择吗&#xff1f;接着往下看你便清楚啦&#xff01; ✮迅捷PPT ☺使用场景&#xff1a;商业演示、教…

dsp c6657 SYS/BIOS学习笔记

1 SYS/BIOS简介 SYS/BIOS是一种用于TI的DSP平台的嵌入式操作系统&#xff08;RTOS&#xff09;。 2 任务 2.1 任务调度 SYS/BIOS任务线程有0-31个优先级&#xff08;默认0-15&#xff0c;优先级0被空闲线程使用&#xff0c;任务最低优先级为1&#xff0c;最高优先级为15&am…

《MySQL DBA 修炼之道》第五章 查询优化

《MySQL DBA 修炼之道》原文是在第六章 查询优化&#xff0c;博主觉得比较重要&#xff0c;所以想提前整理为一篇博文。 查询优化是研发人员比较关注也是疑问最多的领域。 基础知识 1. 查询优化的常用策略 一般的常用策略 优化数据访问、重写SQL、重新设计表、添加索引 4种…

【鸿蒙开发】鸿蒙ArkUI自定义组件如何封装一个好用的Toast/Loading/ProgressHUD组件

1. HUD 在移动端 App 开发中&#xff0c;Toast 、 Loading 和 Progress 是十分常用的UI控件&#xff0c;如果不做特殊要求&#xff0c;一般可以直接使用系统 API 提供的方法&#xff0c;但如果想要定制化 UI&#xff0c;就需要自定义实现了。 在 HarmonyOS 中&#xff0c;Toa…

Leetcode—769. 最多能完成排序的块【中等】

2024每日刷题&#xff08;149&#xff09; Leetcode—769. 最多能完成排序的块 实现代码 class Solution { public:int maxChunksToSorted(vector<int>& arr) {int ans 0;int mx INT_MIN;for(int i 0; i < arr.size(); i) {mx max(arr[i], mx);if(mx i) {a…

单GPU训练一天,Transformer在100位数字加法上就达能到99%准确率

乘法和排序也有效。 自 2017 年被提出以来&#xff0c;Transformer 已成为 AI 大模型的主流架构&#xff0c;一直稳站 C 位。 但所有研究者都不得不承认的是&#xff0c;Transformer 在算数任务中表现非常糟糕&#xff0c;尤其是加法&#xff0c;这一缺陷在很大程度上源于 Tra…

python毕业设计选题求职招聘系统-可视化大屏

✌网站介绍&#xff1a;✌10年项目辅导经验、专注于计算机技术领域学生项目实战辅导。 ✌服务范围&#xff1a;Java(SpringBoo/SSM)、Python、PHP、Nodejs、爬虫、数据可视化、小程序、安卓app、大数据等设计与开发。 ✌服务内容&#xff1a;免费功能设计、免费提供开题答辩P…

虚拟机配置RabbitMQ集群教程

RabbitMQ是常用的一款消息中间件&#xff0c;那么如何在我们虚拟机中创建其集群呢&#xff1f;跟着博主这篇文章让你一步到位 本篇搭建的是三台机器为一个集群&#xff01;假设大家虚拟机都为初始化状态&#xff0c;从0开始&#xff08;注意集群搭建需要CentOS8以上环境&#x…

Linux:基础

一、安装 二、 一些组件 2.1 git管理 集中式版本控制系统:版本库是集中存放在中央服务器的,需要时要先从中央服务器取得最新的版本进行修改,修改后再推送给中央服务器。集中式版本控制系统最大的毛病就是必须联网才能工作,网速慢的话影响太大。 分布式版本控制系统:分布…

Redis的使用场景——热点数据缓存

热点数据缓存 Redis的使用场景——热点数据的缓存 1.1 什么是缓存 为了把一些经常访问的数据&#xff0c;放入缓存中以减少对数据库的访问效率&#xff0c;从而减少数据库的压力&#xff0c;提高程序的性能。【在内存中存储】 1.2 缓存的原理 查询缓存中是否存在对应的数据如…

学习记录day19——数据结构 查找算法

概念 在给定数据元素的某个值&#xff0c;在查找表中确定一个其关键字等于给定值的数据元素的操作&#xff0c;叫做查找 查找的分类 顺序查找:将待查找数据&#xff0c;进行全部遍历一遍&#xff0c;直到找到要查找的元素 折半查找:每次都去除一半的查找范围的查找方式&#x…

Easy es问题总结

官网教程&#xff1a;https://www.easy-es.cn/pages/ac41f0/#settings 一 测试项目 1 pom <dependencies><!-- 排除springboot中内置的es依赖,以防和easy-es中的依赖冲突--><dependency><groupId>org.springframework.boot</groupId><artifa…