上一篇介绍了用于提高元素搜索率的双指针法。本文将再次使用双指针解决leetcoed问题，帮助大家更好的理解和巩固双指针的使用，双指针的具体讲解可以移步【LeetCode系列】15.三数之和1.题目描述给定n个非负整数a1,a2,...,an，每个数代表一个坐标A点(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]输出：492.主题分析在坐标轴上放一个一维数组，数组中每个元素的值为high列的值。从图中可以看出，在坐标轴上排列着不同高度的柱子，不同高度的柱子围成的面积大小就是容器所能容纳的水量。然而，柱子的高度并没有按顺序排列，这导致两个更高的柱子可能彼此靠近并且可能围成更小的区域。计算两根柱子之间的面积：先求两根柱子之间较短的一根作为长方形的一侧h=min{heighti,heightj}两根柱子之间的距离作为长方形的另一边width=j-i长方形的面积等于两条边的乘积。面积=h*宽度Ⅰ。暴力解法为了找到两根柱子并使它们围成最大面积，我们可以通过暴力法嵌套循环，找到所有可能的柱子组合，计算它们的面积，找到最大的面积，时间复杂度为$O(n^2)$。方法代码如下：classSolution{public:intmaxArea(vector&height){intmax_area=0;for(inti=0;imax_area?area:max_area;}}返回最大面积；}};注意：对于第一个循环，i的上限为height.size()-1。对于第二层环流，j的下界为i+1.Ⅱ。双指针法，在暴力解法中，每次固定一个主列，都要遍历剩下的所有列，造成大量元素重复访问。那么有没有办法让我们只扫描一次数组就可以找到最大的区域呢？让我们看看双指针方法是如何工作的。一开始，如果我们用指针i和j指向最末端的列，此时两列之间的距离最大，即我们要找的矩形区域的宽度为最大的。但是最末端的柱子高度不一定是最高的，所以它们组成的长方形的面积也不一定是最大的。因此，我们还需要继续遍历整个数组。这时候我们慢慢的将指针收敛到数组的两端，直到找到最大面积。对于最末端的列，它们之间的宽度已经是最宽的。所以，在收敛的过程中，如果遇到的高度低于两端的柱子，由于构图的宽度较短，面积必然较小，所以我们可以直接跳过，忽略不计。我们只需要考虑那些出现在会聚处的更高高度的支柱。该方法在双指针向中间收敛的过程中只访问数组中的每个元素一次，所以时间复杂度为O(n)。3.手绘讲解代码实现#include#includeusingnamespacestd;intmaxArea(vector&);intmain(){vectortest={1,8,6,2,5,4,8,3,7};intmax=maxArea(测试);cout<<"最大面积为："<&height){inti=0;intj=height.size()-1;int最大面积=0;while(i最大面积?面积：最大面积；while(height[i]<=min_height&&i
