https://oj.leetcode.com/problems/container-with-most-water/
不同高度的柱子排一列,两个柱子可以组成一个容器,求最大容积。
最直观的方法就是暴力,两层for循环,分别遍历头柱子和尾柱子。但是超时了
于是看了discuss,有O(n)的方法。
class Solution { public: int maxArea(vector<int> &height){ if(height.size()<2) return 0; if(height.size()==2) return min(height[0],height[1]); int maxAns = 0; int square = 0; int low = 0, high = height.size()-1; while(low<high) { square = min(height[low],height[high])*(high-low); if(square>maxAns) maxAns = square; if(height[low]<=height[high]) low++; else high--; } return maxAns; } };
证明的话如下:对于low 和high,当 height[low]<hight[high]的时候,low往前前进了一个,这个时候就相当于对 height[low],hight[high-1]没有检查,而如果height[high-1]比hieght[high]大,则还是以height(low)为准,但是宽度上减小了一个,所以面积小了,如果height[high-1]小于height[high]则面积就更小了。所以这个漏掉是安全的。