首页 > 其他分享 >双指针练习:盛水最多的容器

双指针练习:盛水最多的容器

时间:2024-06-02 11:31:12浏览次数:20  
标签:容器 right 盛水 int height width left 指针

题目链接:11.盛水最多的容器

题目描述:

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

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

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

说明:你不能倾斜容器。

解法一(暴力求解)(会超时):

算法思路:

枚举出能构成的所有容器,找出其中容积最大的值。

容器容积的计算方式:

·设两指针 i,j,分别指向水槽版的最左端以及最右端,此时容积宽度为 j - i。由于容器的高度由两板中的短板决定,因此可得容积公式:v = (j - i) * min(height[i] , height[j])

算法代码:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int ret = 0;
        //两层 for 枚举出所有可能出现的情况
        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 = (right - left) * min ( height[right] , height[left] )

容器的左边界为 height[left] ,右边界为 height[right]。

然后我们利用单调性解决此题

我们先举一个例子:

计算初始体积 v1 = (right - left)*min(height[left] , height [right])

接着我们观察:v = 高 * 宽,我们的目的是找最大容积,因此我们可以多举几个

例子,观察规律:

通过移动指针来进行下一个容积的计算:令高为high,宽为width

首先,我们计算初始容积 v = 5 * 6 = 30

无论我们移动left 还是right ,宽度width都会变小

        如果移动left,width变小,高也会变小(6 -> 2)

        如果移动right,width变小,高也会变小(6 -> 4)

由此可看无论怎么移动 v 都会变小,这里可以总结一个规律:如果移动之后的数,小于left与right原先所对应的值,那么这个新的v,一定比原来小 

如果移动之后的数比原来的大,那么高度是不变的,width是变小的,因此v变小

因此,总结出两种情况;

        v = high*width

        1️⃣high 不变 ,width减小 ,v减小        

        2️⃣high减小,width减小,v减小

我们假设左边界最小,那么此时移动left,遇到的数比left大,就会改变高度最小值(2->5),这样v就有可能增大

当我们不断重复上述过程,每次都可以舍去大量不必要的枚举过程,直到left 与 right相遇,期间产生的所有容积里面的最大值,就是最终答案

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0,right = height.size()-1,ret = 0;
        //容器体积一定大于0,所以这里可以设置为0
        while(left < right){
            //记录v的值
            //学会使用库函数,max,min
            int v = min(height[left],height[right]) * (right - left);
            ret = max(ret,v);//找大值,并更新

            if(height[left] <= height[right]){
                left++;
            }else right--;
        }

        return ret;
    }
};

标签:容器,right,盛水,int,height,width,left,指针
From: https://blog.csdn.net/2202_75331338/article/details/139387110

相关文章

  • 双指针练习:复写0
    1.题目链接:1089.复写零2.题目描述:给你一个长度固定的整数数组 arr ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。3.解法(原地复写-双指针):算法......
  • C++实现自定义容器类型的范围循环
    先看一下类的设计与实现:classMyStack{public:MyStack()=default;MyStack(int*p,size_tlen):d(p),size(len){}int*begin(){returnd;}int*end(){return&d[size];}private:int*d=nullptr;size_tsize......
  • 指针的详解延续二
     第一篇移步CSDNhttps://mp.csdn.net/mp_blog/creation/editor/139301675 第二篇移步CSDN​​​​​​​​​​​https://mp.csdn.net/mp_blog/creation/editor/139329194目录一、指针数组二、字符指针变量三、数组指针变量四、二维数组传参的本质五、函数指针变量 ......
  • 旅行第五天【算法】双指针-----三数之和+四数之和
    文章目录一、题目二、算法原理三、编写代码四、题目五、算法原理六、编写代码一、题目链接:三数之和二、算法原理首先是解法一:暴力解法(其实有必要思考一下,不用把程序写出来,写伪代码就可以了,因为优化后算法的代码是建立在暴力解法的基础上的)三个指针,分别依次......
  • 《C++primer》读书笔记---第九章:顺序容器
    9.1顺序容器概述下表列出了标准库的顺序容器,所有容器都提供了快速顺序访问元素的能力:多种容器中,通常使用vector是最好的选择,除非你有很好的理由选则其他容器。以下是一些选择容器的基本原则:除非你有很好的理由选择其他容器,否则选择vector如果你的程序有很多小的元素,且空......
  • 深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
    在本篇文章中,我们将详细解读力扣第170题“两数之和III-数据结构设计”。通过学习本篇文章,读者将掌握如何设计一个数据结构来支持两种操作,并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释和ASCII图解,以便于理解。问题描述力扣第170题“两数之和III......
  • 【C/C++】--- 指针详解 2.0
    接下来进入指针的进阶部分,准备好大脑补充:(重点)数组名是数组首元素地址数组首元素地址和数组地址,值相同,但本质不同,区别在于二者的类型不相同比如数组intarr[10];数组首元素地址的类型:首先这是一个地址所以要用指针接收,(),然后是地址指向元素的类型为int,所以这个指针的......
  • day1 指针学习
    一指针的定义方法1.1简单指针数据类型*指针变量名称intp//定义了一个指针变量,为整形在定义指针变量时,是用来修饰变量的,说明变量p是一个指针变量。变量名是p2关于指针的运算符&为取地址符,*:在定义一个指针变量时,起到标识的作用,标识定义的是一个指针变量,除此之外其他地方......
  • 在Linux中,如何进行容器技术的应用?
    在Linux中应用容器技术主要是通过Docker或类似的容器管理系统来实现的。容器技术允许你将应用程序及其依赖打包在轻量级、可移植的容器中,实现快速部署和隔离运行。以下是使用Docker进行容器技术应用的步骤:1.安装Docker首先,需要在Linux系统上安装Docker。对于基于Debian的系统(如......
  • C++ 智能指针学习笔记
    1、为什么使用智能指针?    一句话就是为了防止内存泄漏。voidremodel(std::string&str){std::string*ps=newstd::string(str)...str=ps;return;}    举个例子,如上面代码,每当调用时,该函数都分配堆内的内存,但从不收回,从而导致......