【算法专题突破】双指针 - 盛最多水的容器(4)

简介: 【算法专题突破】双指针 - 盛最多水的容器(4)

1. 题目解析

题目链接:11. 盛最多水的容器 - 力扣(Leetcode)

这道题目也不难理解,

两边的柱子的盛水量是根据短的那边的柱子决定的,

而盛水量就是短的柱子的高度 * 宽度即可。

2. 算法原理

这道题可以用暴力枚举,两层for循环,肯定是可以找到最大的盛水量,

但是作为一道中等题,用暴力会超时,所以我们得想一个更好的解法。

我们来观察一下规律:

以这个图为例;

如果我们让比较高的左边往右遍历,会有两种情况:

1. 如果右边的柱子更高,而宽度变小,盛水量减少,

2. 如果右边的柱子更矮,宽度又变小,盛水量减少。

很明显不太行,

那如果我们让比较矮的右边往左遍历,也会有两种情况:

1. 如果左边的柱子更高,宽度变小,盛水量可能变小,可能不变,可能变大,

2. 如果左边的柱子更矮,宽度变小,盛水量减少。

从上面两种情况来看,我们可以通过不断让矮的一边的柱子往中间遍历,

记录每次出现的最大值,当遍历完之后,我们就能得到最大值了,

而我们只遍历了一遍,所以时间复杂度就优化到了O(N),

具体做法就是使用双指针来维护两边。

3. 代码编写

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, maxVal = 0;
        while(left < right) {
            maxVal = max(maxVal, min(height[left], height[right]) * (right - left));
            if(height[left] < height[right]) left++;
            else right--;
        }
        return maxVal;
    }
};

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

目录
打赏
0
0
0
0
339
分享
相关文章
【算法】——双指针算法合集(力扣)
移动零,复写零,快乐数,盛最多水的容器,有效三角形的个数,和为s的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
双指针算法详解
本文介绍了双指针算法及其应用。双指针算法是在数组或字符串中常用的高效技术,通过维护两个指针遍历数据结构以解决特定问题。根据指针移动方向,可分为同向双指针、相向双指针和快慢指针。同向双指针如移动零和复写零问题;快慢指针如快乐数问题;相向双指针如盛水最多的容器、有效三角形数量及多数之和等问题。通过合理运用双指针技巧,可简化代码并提高效率。
134 4
【算法】双指针
【算法】双指针
基于和声搜索优化算法的机器工作调度matlab仿真,输出甘特图
本程序基于和声搜索优化算法(Harmony Search, HS),实现机器工作调度的MATLAB仿真,输出甘特图展示调度结果。算法通过模拟音乐家即兴演奏寻找最佳和声的过程,优化任务在不同机器上的执行顺序,以最小化完成时间和最大化资源利用率为目标。程序适用于MATLAB 2022A版本,运行后无水印。核心参数包括和声记忆大小(HMS)等,适应度函数用于建模优化目标。附带完整代码与运行结果展示。
基于AES的遥感图像加密算法matlab仿真
本程序基于MATLAB 2022a实现,采用AES算法对遥感图像进行加密与解密。主要步骤包括:将彩色图像灰度化并重置大小为256×256像素,通过AES的字节替换、行移位、列混合及轮密钥加等操作完成加密,随后进行解密并验证图像质量(如PSNR值)。实验结果展示了原图、加密图和解密图,分析了图像直方图、相关性及熵的变化,确保加密安全性与解密后图像质量。该方法适用于保护遥感图像中的敏感信息,在军事、环境监测等领域具有重要应用价值。
基于免疫算法的最优物流仓储点选址方案MATLAB仿真
本程序基于免疫算法实现物流仓储点选址优化,并通过MATLAB 2022A仿真展示结果。核心代码包括收敛曲线绘制、最优派送路线规划及可视化。算法模拟生物免疫系统,通过多样性生成、亲和力评价、选择、克隆、变异和抑制机制,高效搜索最优解。解决了物流仓储点选址这一复杂多目标优化问题,显著提升物流效率与服务质量。附完整无水印运行结果图示。
基于免疫算法的最优物流仓储点选址方案MATLAB仿真
基于GA遗传优化TCN-GRU时间卷积神经网络时间序列预测算法matlab仿真
本项目基于MATLAB2022a开发,提供无水印算法运行效果预览及核心程序(含详细中文注释与操作视频)。通过结合时间卷积神经网络(TCN)和遗传算法(GA),实现复杂非线性时间序列的高精度预测。TCN利用因果卷积层与残差连接提取时间特征,GA优化超参数(如卷积核大小、层数等),显著提升模型性能。项目涵盖理论概述、程序代码及完整实现流程,适用于金融、气象、工业等领域的时间序列预测任务。
基于遗传优化算法的多AGV栅格地图路径规划matlab仿真
本程序基于遗传优化算法实现多AGV栅格地图路径规划的MATLAB仿真(测试版本:MATLAB2022A)。支持单个及多个AGV路径规划,输出路径结果与收敛曲线。核心程序代码完整,无水印。算法适用于现代工业与物流场景,通过模拟自然进化机制(选择、交叉、变异)解决复杂环境下的路径优化问题,有效提升效率并避免碰撞。适合学习研究多AGV系统路径规划技术。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等