好吧这个题我直接想没想出来,断断续续,后来忍不住去看了别人的思路。
先说说我的想法吧。
第一种思想就是暴力,每两个线段我都选出来,求个容积比一下,选最大。
思路逻辑都没错,但是超时了。我看了看test case数据量挺大的。
接下来怎么办呢,肯定要找到低于n^2复杂度的方法才有可能过。
想了好久,排序?自下而上的倒水?两个指针,左边一个右边一个,像内移动?或者我左边固定,认为另外一条线一定在其右边来找?挺乱的。
最后看了别人的想法,真心so easy,不过自己也够脑残的,怎么能想不到呢?呵呵呵?
方法很简单,贪心
两个指针左右各一个,然后记录容积。长度较小的那个线段的指针向内移动,网上的人说这个是twosum求法,自己还是太水了。
再具体实现的时候,因为涉及到两个线段相等的情况,这个时候可能移动左边的,可能移动右边的,所以最好的办法是:写个递归。
附上代码,A题很受折磨,特别是对我这种老年人啊,加油啊!
class Solution { public: int sum; int maxArea(vector<int> &height) { // Note: The Solution object is instantiated only once and is reused by each test case. sum = 0; int left = 0; int right = height.size() - 1; func(left,right,height); return sum; } void func(int left,int right,vector<int>&height) { if(left < right) { int min = height[left]; if(min > height[right]) min = height[right]; int tmp = min * (right-left); if(tmp > sum) sum = tmp; if(height[left] > height[right]) { func(left,right-1,height); } else if(height[left] < height[right]) { func(left+1,right,height); } else { func(left+1,right,height); func(left,right-1,height); } } } };