精选50题之 11. 盛最多水的容器

腾讯精选练习50 题之 11. 盛最多水的容器原题目链接直接尝试题目分析解题思路代码实现写在最后原题目链接给定 n 个非负整数 a1a2…an每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。说明你不能倾斜容器且 n 的值至少为 2。图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。示例:输入: [1,8,6,2,5,4,8,3,7]输出: 49直接尝试最直观的思路是在所有组合中找到最大值即暴力求解。classSolution{public:intmaxArea(vectorintheight){intarea0;for(inti0;iheight.size();i){for(intji1;jheight.size();j){areamax(area,min(height[i],height[j])*(j-i));}}returnarea;}};复杂度分析时间复杂度O(n^2)空间复杂度O(1)恒定常数量级。于是乎运行结果…PS.本来还想优化结果一看实例 1~15000 的连续数组放弃了…题目分析暴力算法完败说明思路出现了问题一定有其它方式。回到原题目容器大小是由长度和高度决定实际上是双变量问题。为使容积增大无非增加长度or增加高度。由于各个位置高度其实已经给出那么自变量可以认为是长度。也就是双指针法解题思路从长度最大时开始向中间收拢选择高度较短的一个作为高度进行求解顺序比较纪录最大值。代码实现classSolution{public:intmaxArea(vectorintheight){intarea0,l0,rheight.size()-1;while(lr){areamax(area,min(height[r],height[l])*(r-l));if(height[l]height[r])l;elser--;}returnarea;}};运行结果效果显著优化参考8msclassSolution{public:intmaxArea(vectorintheight){intl0;inthheight.size()-1;intmax0;while(lh){intmmin(height[l],height[h])*(h-l);maxmaxm?max:m;if(height[l]height[h])h--;elsel;}returnmax;}};写在最后周末愉快~