11. 盛最多水的容器(c++题解)

这篇具有很好参考价值的文章主要介绍了11. 盛最多水的容器(c++题解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

11. 盛最多水的容器(c++题解)

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。

示例 1:

11. 盛最多水的容器(c++题解),力扣刷题,C++,c++,算法,数据结构,双指针
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2:

输入:height = [1,1]
输出:1

提示:
n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

思路

这道题最开始的思路只有暴力解,就是用两个for循环来一个一个试,但是结果发现这样是错的。后续改进的方法就是双指针,也就是两个指针l,r分别指向最左边和最右边,两个指针对应的垂线较小的指针想前移动,这样就能保证每次移动的都是较小的指针,两者之间的面积也会不断的找到最大的情况。

复杂度

时间复杂度:
O(n)

空间复杂度:
O(1)

Code

C++文章来源地址https://www.toymoban.com/news/detail-675187.html

// 双重for循环的做法,结果超时了
// class Solution {
// public:
//     int maxArea(vector<int>& height) {
//         int max=0;
//         for(int i=0;i<height.size();i++){
//             for(int j=i+1;j<height.size();j++){
//                 int h = min(height[i],height[j]);
//                 int s=h*(j-i);
//                 if(s>max){
//                     max=s;
//                 }
//             }
//         }
//         return max;

//     }
// };


//双指针的方法
class Solution {
public:
    int maxArea(vector<int>& height) {
        int max=0,s=0;
        int l=0,r=height.size()-1;
        while(l<r){
            if(height[r]>height[l]){
                s=height[r]*(r-l);
                r--;
            }
            else{
                s=height[l]*(r-l);
                l++;
            }
            if(max<s) max=s;
        }
        return max;

    }
};

到了这里,关于11. 盛最多水的容器(c++题解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法——双指针】LeetCode 11 盛最多水的容器

    题目描述: 解题思路:         如图所示:         1、我们考虑相距最远的两个柱子所能容纳水的面积。宽度是两根柱子之间的距离8;高度取决于两根柱子之间较短的那个,即左边柱子的高度3。水的面积就是3×8=24。         2、如果选择固定一根柱子,另外一根

    2024年02月12日
    浏览(32)
  • 【算法|双指针系列No.4】leetcode11. 盛最多水的容器

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月06日
    浏览(48)
  • 力扣-盛最多水的容器

    11.盛最多水的容器 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。 说明:你不能倾斜容器 示例1: 示例 2: 分析: 题解

    2024年01月15日
    浏览(41)
  • 【算法专题--双指针算法】leecode-202. 快乐数(medium)、leecode-11. 盛最多水的容器(medium)

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 双指针 常见的双指针有两种形式,一种是对撞指针,⼀种是左右指针。 对撞指针:一般用于顺序结构中

    2024年03月23日
    浏览(38)
  • 11. 盛最多水的容器

    给定一个长度为  n  的整数数组  height  。有  n  条垂线,第  i  条线的两个端点是  (i, 0)  和  (i, height[i])  。 找出其中的两条线,使得它们与  x  轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明: 你不能倾斜容器。 示例 1: 示例 2: 提示

    2024年01月20日
    浏览(57)
  • leetcode 11. 盛最多水的容器

    leetcode 11. 盛最多水的容器 解题思路 :双指针 每次向内移动矮的指针,因为如果向内移动高的指针,面积一定会变小;如果向内移动矮的指针,面积还有可能变大。

    2024年02月06日
    浏览(44)
  • LeetCode_11. 盛最多水的容器

    11. 盛最多水的容器 - 力扣(LeetCode) https://leetcode.cn/problems/container-with-most-water/         这题就是典型的是一道很经典的面试题,最优的解法是双指针,但很多人在第一次看到这题的时候很难想到用双指针来解(比如我)。好了,话不多说上解法: 首先我们设两个left和righ

    2024年02月14日
    浏览(39)
  • LeetCode_11_中等_盛最多水的容器

    给定一个长度为 n n n 的整数数组 h e i g h t height h e i g h t 。有 n n n 条垂线,第 i i i 条线的两个端点是 ( i , 0 ) (i, 0) ( i , 0 ) 和 ( i , h e i g h t [ i ] ) (i, height[i]) ( i , h e i g h t [ i ]) 。 找出其中的两条线,使得它们与 x x x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的

    2024年01月24日
    浏览(47)
  • 【算法专题】双指针—盛最多水的容器

      分析这个题目不难得出一个 容积公式   解法一:暴力枚举(超时) 套用上述的容积公式,使用 两个for循环 来枚举出所有可能的情况,再挑出最大值即可,但是这种写法会超时,导致不通过。时间复杂度是O(n^2) 可以自己去尝试一下。  解法二:双指针  设两个指针 left,

    2024年02月06日
    浏览(49)
  • 【算法】双指针求解盛最多水的容器

    Problem: 11. 盛最多水的容器 首先我们来解析一下本题 题目中说到,要找出其中的两条线, 使得它们与 x 轴共同构成的容器可以容纳最多的水 。 那我们现在来看最外侧的两根,一个高度为8,一个则为7,那我们肯定选择高度为7的, 如果选择8的话就会出现溢出的问题 ;我们这

    2024年02月11日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包