首页 > 其他分享 >【LeetCode Hot 100】11. 盛最多水的容器

【LeetCode Hot 100】11. 盛最多水的容器

时间:2024-09-20 22:24:14浏览次数:10  
标签:11 容器 area int res height Hot 最多水 指针

题目描述

首先记录一下题目的解法。使用双指针记录容器的边界,从边界最大的容器开始,i位于最左侧,j位于最右侧。每次向中间移动高度较小的那个指针,并使用一个变量res记录容器最大的容积(即最终的答案)。

// C++
class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1;
        int res = 0;
        while (i < j) {
            int area = (j - i) * min(height[i], height[j]);
            res = max(res, area);
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return res;
    }
};

// Java
class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1;
        int res = 0;
        while (i < j) {
            int area = j - i;
            if (height[i] < height[j]) {
                area *= height[i];
                res = Math.max(res, area);
                i++;
            } else {
                area *= height[j];
                res = Math.max(res, area);
                j--;
            }
        }
        return res;
    }
}

官方的题解中解释了这种做法的正确性。我在这里记录一下我的直观想法。对于这种题目,最粗暴的想法自然是使用双重循环遍历每一种边界下标组合,记录最大的那个答案,显然对于较大的数据量来说,这种做法的时间复杂度为平方级,很容易超时。那么我们该如何进行剪枝,跳过一些情况的判断呢?将两个指针放在最远的两端开始向中间靠拢,\(S=(j-i) \times min(h_i, h_j)\),当指针向中间移动时,第一个乘数项一定变小,要想让整体的面积(容器的容积)变大,第二个乘数就只能变大,如果我们移动高度较大的那个指针(假设height[i] < height[j],我们移动j),\(min(h_i,h_j)\)这一项仍然由高度较小(即iheight[i])的那一项决定,也就是说移动高度较大的指针不会使这一项变大,当且仅当我们移动高度较小的那个指针时,才有可能使得此项变大。这也是为什么我们每次移动其中一个指针的原因。

标签:11,容器,area,int,res,height,Hot,最多水,指针
From: https://www.cnblogs.com/louistang0524/p/18423400

相关文章

  • P2414 [NOI2011] 阿狸的打字机
    题目思路将每一个输出的串放入一个Trie树中。考虑离线处理询问\((x,y)\),对于每一个\(y\)集中处理所有的\(x\),\(y\)在Trie树上走,走过的点标记一下,结果就是\(x\)字符串结尾节点在fail树上的对应节点的子树的标记数量。记得在节点离开的时候撤销标记。代码#incl......
  • 教你几招,轻松设置Win11右键恢复旧版模样
    大家好!今天要教大家如何把Win11右键菜单变回完整的展开模式哦!其实很简单,只要在Windows开始图标下面的运行里输入一段代码就可以啦!接下来就让我来详细地跟大家分享一下这个方法吧!Win11右键菜单恢复为完整展开模式的方法1、首先,按键盘上的【Win+X】组合键,或右键......
  • 1.1 elasticsearch分布式集群基本搭建(centos7.x + elaticsearch7.11.1)
    【1】分布式分片集群基础概念【1.1】ES的分布式集群有什么用?高可用高可用(HighAvailability)是分布式系统架构设计中必须考虑的因素之一,它通常是指,通过设计减少系统不能提供服务的时间。如果系统每运行100个时间单位,会有1个时间单位无法提供服务,我们说系统的可用性是9......
  • P11063 【MX-X4-T3】「Jason-1」数对变换
    题意你有一个有序数对\((x,y)\),每次你可以选择其中一个数并指定一个整数\(k\),然后将你选的那个数除以\(k\)下取整,另外一个数乘\(k\)。你现在想要把\((a,b)\)变换成\((c,d)\)构造一组在65步解决问题的方案,或报告无解。\(1\lea,b,c,d\le10^9\)分析这题的突破口在于......
  • 探索未来智能:Moonshot AI 引领AI新纪元——M1超级模型
    在人工智能的快速演进中,MoonshotAI再次站在了技术创新的前沿。推出M1超级模型,这是一款旨在突破现有AI能力极限的革命性产品。M1超级模型的诞生背景随着数据量的爆炸性增长和计算能力的提升,AI模型正变得越来越复杂和强大。M1超级模型的诞生是对这一趋势的直接响应,它代表了Moons......
  • C++11
    1.C++11简介在2003年C++标准委员会曾经提交了一份技术勘误表(简称TC1),使得C++03这个名字已经取代了C++98称为C++11之前的最新C++标准名称。不过由于C++03(TC1)主要是对C++98标准中的漏洞进行修复,语言的核心部分则没有改动,因此人们习惯性的把两个标准合并称为C++98/03标准。......
  • Advanced .Net Debugging 11:完结篇
    一、介绍这是我的《Advanced.NetDebugging》这个系列的第十一篇文章,也是这个系列的最后一篇了。我已经把原书的前八章内容全部写完了,本来打算继续写第九章和第十章的内容,后来我放弃逐章逐节的编写,选择了将两章的内容进行过滤后,合为一篇,只把重要的内容包含进来的做法。原......
  • 11 UML中的逻辑视图、进程视图、实现视图、部署视图
    UML(UnifiedModelingLanguage,统一建模语言)是一种用于对软件密集系统进行可视化建模的标准语言。在UML中,系统可以从不同的角度进行描述,这些不同的角度被称为视图。具体来说,UML中的逻辑视图、进程视图、实现视图和部署视图分别代表了系统的不同方面。1.逻辑视图(LogicalView)定义......
  • 联邦快递跌超11%,FBX福币加密货币市场官网分析耐克涨超7%
    9月20日,美股夜盘时段,联邦快递跌超11%,公司第一财季盈利剧减逾20%,下调全年业绩指引。FBX福币凭借用户友好的界面和对透明度的承诺,迅速在加密货币市场中崭露头角耐克涨超7%,公司任命前高管埃利奥特·希尔为首席执行官。 9月19日电周四,A股三大股指高开震荡,深证成指、创业板......
  • C++标准的一些特性记录:C++11的thread_local
    文章目录thread_localthread_local在多线程的编程环境里,一般来说,所有的线程都是共享同一个内存空间,也就是说如果定义一个变量,这个变量是被所有线程共享的,所以多个变量在访问同一个变量时,是需要加锁机制的,否则就会出现问题。在C++11中,引入了一个关键字thread_local......