免费情感网站哪个好,企业为什么做网站 图片,企业网站制作流程,手机建设网站目的个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 点解直接跳转到该题目 目录 1️⃣题目描述2️⃣算法分析3️⃣代码编写 1️⃣题目描述
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。
示例1 输入[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.length2 n 1050 height[i] 104
2️⃣算法分析
通过不断地调整较短的边界来寻找可能的最大容量。因为容器的容量受限于较短的边界所以选择移动较短的边界可以增加容器的高度有可能得到更大的容量。通过不断缩小指针之间的宽度直到指针重合即可得到最大容量。
容器容量v s * h由于我们这里不断移动两个“指针”所以 s 是不断变小的那么问题来了我们要移动哪个指针呢是向右移动左指针的还是向左移动右指针呢我们要知道无论我们移动哪一个指针容器的 s 都是减小的此时如果要使得容器容量增大我们需要移动指针指向的值较小的那个指针。举个例子19我们此时就需要向右移动左指针了因为我们只有移动左指针才有可能使得容器的容器容量变大即通过增加h的方式。 即
if(height[l] height[r]) l;
else r--; 3️⃣代码编写
class Solution {
public:int maxArea(vectorint height) {int l 0,r height.size() - 1,ret 0;while(l r){int v (r - l) * min(height[l],height[r]);ret max(v,ret);if(height[l] height[r]) l;else r--; }return ret;}
};
