网站建设与管理期末试卷,重庆市工程造价信息价查询,叙述网站建设的流程,莱芜专注搜狗推广LeetCode原题链接#xff1a;盛水最多的容器
下面是题目描述#xff1a; 给定一个长度为 n 的整数数组 height 。有 n 条垂线#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。…LeetCode原题链接盛水最多的容器
下面是题目描述 给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。 示例1 输入[1,8,6,2,5,4,8,3,7] 输出49
示例1图
解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。
示例 2 输入height [1,1] 输出1
提示 n height.length 2 n 105 0 height[i] 104
1、解题思路 求解本题当然也可暴力枚举但本文主要通过这道题进行双指针算法的学习故这里直接进行双指针算法的讲解。
虽说是双指针但求解本题更重要的是对其单调性规律的发现和运用
首先明确体积的计算为V w * hw是数组中两个数据的距离h是这两数据中较小的一个木桶效应也是解出本题的关键
接下来关键点来了此时 “固定” 较小的h而将h中较大的向内枚举也就是让w减小那么枚举的过程有且仅有以下两种情况 1w减小了新的h比原来那个较小的h大此时据木桶效应仍以原来那个较小的h为计算体积的h故此时计算V w * hw减小h不变V一定减小 2w减小了新的h比原来那个较小的h小此时据木桶效应以新的较小的h为计算体积的h故此时计算V w * hw减小h减小V一定减小
以上就前面所说的单调性规律接下来的问题就是如何利用这个规律通过双指针进行枚举解答
那么这里通过示例1 数组height [1,8,6,2,5,4,8,3,7] 进行说明
这里的双指针更具体来说是对撞指针所以让一个指针指向数组的第一个数据设指针为front下标为0另一个指针指向最后一个数据设指针为back下标为7开始枚举 1初始时可得宽度为w back - fronth取较小者也就是height[front]将它们相乘得到一个体积值V1根据单调性下一步若将back向前向内移进行枚举直至第一个数据算出来的体积一定都小于V1w一直在减小h要么不变要么更小故此时不应让back向前而应让front向后向内移动进行枚举。
虽然front向后宽度也一定是减小的但h有可能变大且变大的幅度远超w减小的幅度而让总体积增大。
此时我们就可以得到两个指针移动的规律了让高度小的指针向内移动枚举即若front对应在数组中的数据大于等于back在数组中的数据即height[front] height[back] 就让back--反之则让front
2通过上面的分析下一步是front后我们计算出第二个体积V2然后重复上述过程每一步都能算出一个体积最后这些体积中最大的即为问题的解。
2、具体代码
int maxArea(vectorint height) {int front 0;int back height.size() - 1;int resArea 0;while(front ! back){int area (back - front) * (height[front] height[back] ? height[front] : height[back]);if(area resArea){resArea area;}if(height[front] height[back]){front;}else{back--; }}return resArea;}看完觉得有觉得帮助的话不妨点赞收藏鼓励一下有疑问或看不懂的地方或有可优化的部分还恳请朋友们留个评论多多指点谢谢朋友们
