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

腾讯精选练习（50 题）之 11. 盛最多水的容器

    • 原题目链接
    • 直接尝试
    • 题目分析
    • 解题思路
    • 代码实现
    • 写在最后

原题目链接

给定 n 个非负整数 a1，a2，…，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(vector<int>&height){intarea=0;for(inti=0;i<height.size();i++){for(intj=i+1;j<height.size();j++){area=max(area,min(height[i],height[j])*(j-i));}}returnarea;}};

复杂度分析：

于是乎，运行结果…

PS.本来还想优化，结果一看实例 1~15000 的连续数组，放弃了…

题目分析

暴力算法完败，说明思路出现了问题，一定有其它方式。
回到原题目，容器大小是由长度和高度决定，实际上是双变量问题。为使容积增大，无非增加长度or增加高度。由于各个位置高度其实已经给出，那么自变量可以认为是长度。
也就是：双指针法

解题思路

从长度最大时开始，向中间收拢，选择高度较短的一个作为高度进行求解，顺序比较，纪录最大值。

代码实现

classSolution{public:intmaxArea(vector<int>&height){intarea=0,l=0,r=height.size()-1;while(l<r){area=max(area,min(height[r],height[l])*(r-l));if(height[l]<height[r])l++;elser--;}returnarea;}};

运行结果，效果显著

优化参考：8ms

classSolution{public:intmaxArea(vector<int>&height){intl=0;inth=height.size()-1;intmax=0;while(l<h){intm=min(height[l],height[h])*(h-l);max=max>=m?max:m;if(height[l]>height[h])h--;elsel++;}returnmax;}};

写在最后

周末愉快~