首页 > 其他分享 >LeetCode 11.盛最多的水(双指针,贪心)

LeetCode 11.盛最多的水(双指针,贪心)

时间:2024-03-26 21:29:37浏览次数:26  
标签:11 减小 下标 高度 不变 水量 移动 LeetCode 贪心

题目

思路

我们可以安排俩个指针(数组下标)放在数组的头部和尾部;

每次移动高度较低的下标,判断是否为最大水量并记录;

(水量=下标差乘较小高度)

证明可行性

如果移动高度较高的下标,由于下标差减小,故不论后面下标对应的高度增大,不变或减小都

会导致水量减小;

(增大:下标差减小,较小高度仍不变)

(不变:下标差减小,较小高度不变)

(减小:下标差减小,较小高度可能减小也可能不变)

如果移动高度较小的下标,当下一个下标对应高度增大时,水量便有可能增大;

!!!

对于高度较高的下标,可能存在另一高度与它组成最大水量,

如果移动便丢失了最大水量;

对于高度较低的下标,即便后面会出现更大的水量,但由于下标差的减小,新出现的最大水量

中的较低下标也不可能是原较低下标;

故我们可以放心移动高度较低的下标;

当俩高度一致时,如果有更大的水量出现,那么在俩高度之间必然存在至少俩个更高的高度,不管移动哪边只要我们接着使用高度较低移动原则任可遍历到

代码:

标签:11,减小,下标,高度,不变,水量,移动,LeetCode,贪心
From: https://blog.csdn.net/lyy_222/article/details/136995505

相关文章

  • LeetCode刷题Day11(补卡)
    20.有效的括号题目链接:leetcode20.有效的括号文章讲解:代码随想录视频讲解:哔哩哔哩视频这题考察的是栈的使用,遍历字符串,如果是左括号存入栈中,如果是右括号则对比栈的头部是否为与之匹配的左括号,如果不是则返回false,最后若栈为空则正好匹配返回true,详细代码如下:cl......
  • leetcode:链表的中间节点
    快慢指针快的到了末尾,慢的所指的就是中点你一开始写的时候while里面,fast.next放在前面,报错,空指针应该写在后面,对于偶数个元素的链表而言/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode......
  • Windows Packet Divert(WinDivert)是一个适用于Windows 10、Windows 11和Windows Server
    WindowsPacketDivert(WinDivert)是一个适用于Windows10、Windows11和WindowsServer的用户模式数据包捕获和重定向工具。WinDivert允许用户模式应用程序捕获/修改/丢弃发送到/从Windows网络堆栈的网络数据包。总之,WinDivert可以:捕获网络数据包过滤/丢弃网络数据包嗅探......
  • 面对对象11:方法重写
    packagecom.oop;importcom.oop.demo05.A;importcom.oop.demo05.B;/**封装的意义*1.提高程序的安全性*2.隐藏代码的实现细节*3.统一接口*4.系统的可维护性增加了**/publicclassApplication{//静态方法和非静态方法区别很大!!!//有static时,b调用B......
  • Win11专业版永久密钥(支持重装)
    Windows11专业版是Windows11的商业版本,专为中小型企业(SMB)和教育机构设计。它提供了一些家庭版中没有的功能,例如:高级安全功能:包括BitLocker加密、WindowsDefender高级威胁防护和WindowsHelloforBusiness。设备管理功能:包括组策略、WindowsUpdateforBusines......
  • CF1411C - Peaceful Rooks | 思维
    links在一个\(n\timesn\)的棋盘上有\(m(m<n)\)个棋子。若棋子处于同一行或同一列便认为他们可以互相攻击。初始时棋子之间均不可互相攻击。你可以进行若干次操作,每次操作可以将棋子纵向移动任意格或横向移动任意格,要求移动之后棋子之间不能互相攻击。求使得棋子均处在主......
  • 代码随想录算法训练营day34 | leetcode 1005. K 次取反后最大化的数组和、134. 加油站
    目录题目链接:1005.K次取反后最大化的数组和-简单题目链接:134.加油站-中等题目链接:135.分发糖果-困难题目链接:1005.K次取反后最大化的数组和-简单题目描述:给你一个整数数组nums和一个整数k,按以下方法修改该数组:选择某个下标i并将nums[i]替换为-nums[i]。重......
  • LeetCodeHot100 数组 53. 最大子数组和 56. 合并区间 238. 除自身以外数组的乘积
    53.最大子数组和https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-likedpublicintmaxSubArray(int[]nums){int[]dp=newint[nums.length];dp[0]=nums[0];for(inti=1;i<nums......
  • 2024.03.11 校招 实习 内推 面经
    绿*泡*泡VX:neituijunsir  交流*裙,内推/实习/校招汇总表格1、校招|微软2024春招正式开启!校招|微软2024春招正式开启!2、社招&校招|主线科技Trunk春季热招中(内推)社招&校招|主线科技Trunk春季热招中(内推)3、校招|思特威2024春季校招正式启动(内推)校招|......
  • 011、送綦毋潜落第还乡
    011、送綦毋潜落第还乡唐●王维圣代无隐者,英灵尽来归。遂令东山客,不得顾采薇。既至金门远,孰云吾道非。江淮度寒食,京洛缝春衣。置酒长安道,同心与我违。行当浮桂棹,未几拂荆扉。远树带行客,孤城当落晖吾谋适不用,勿谓知音稀。 【现代诗意译】送綦友人落第回乡 圣明的时......