给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明你不能倾斜容器。分析求最大水量就是求最大容积长方形的面积很容易得出是长乘宽Si长*k宽i是两个点之间的距离k是两条长边最短的那条边因为水箱容器所能储存的水肯定是和短边齐平的暴力算法 首先先尝试最简单思路就是双重for循环遍历求最大值class Solution { 2public: 3 int maxArea(vectorint height) { 4 int sum0; 5 for(int i0;iheight.size();i) 6 { 7 for(int j0;jheight.size();j) 8 { 9 int xj-i; 10 int ymin(height[j]-height[i]); 11 if( x*ysum) 12 { 13 sum x*y; 14 } 15 16 17 } 18 } 19 return sum; 20 } 21};可以看到大部分案例都通过了证明逻辑上可行但是还有几个没通过。查看没通过的案例可以直接看出是因为案例数组太到双重for循环的时间规模是n²所以运行超时了。双指针法 想办法把双重for循环降为单层for循环因为遍历数组是我们肯定要做的事情不做就没办法得到具体的高度了。设置双指针i,j,i代表数组开头j代表数组末尾双指针一个头一个尾开始计算最大水箱值。左指针i在最左端右指针j在最右端。每次计算当前面积然后移动高度更小的那一侧指针如果height[i] height[j]移动左指针i解释当前 是短板。如果移动右指针宽度一定会变小而容器高度最高只能是 height [i]面积只会更小没有必要。所以只能移动短板才有可能得到更大高度获得更大面积。如果height[j] height[i]移动右指针j--长板向内收缩不会带来收益短板向内收缩才有机会提升容器高度class Solution { public: int maxArea(vectorint height) { int sum0; int i0; int jheight.size()-1; while(ij) { int xj-i; int y min(height[i],height[j]); if(x*ysum) { sumx*y; } if(height[i]height[j]) { i; } else { j--; } } return sum; } };
