11. Container With Most Water

题意

给定n个非负整数$a_1,a_2,…,a_n$,其中每个数表示坐标点$(i,a_i)$,i是数组下标,$a_i$是对应高度.寻找两条线,使得两条线构成的长方形面积最大,盛水最多.

Example:

Input: [1,8,6,2,5,4,8,3,7] Output: 49

暴力破解

对每种情况进行循环,计算对应的面积,同时保存最大的面积.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int maxArea(vector<int>& height) {
if (height.size()<2)
return 0;
int res = 0;
for(int i=0;i<height.size();i++){
for(int j=i+1;j<height.size();j++){
int minH = min(height[i], height[j]);
res = max(res, minH*(j-i));
}
}
return res;
}
};

时间复杂度O(N*N).时间复杂度太高.而复杂度太高主要是进行了一些实际上并不需要的计算,尽管利用对称性,减少了一半的计算量.

双指针

思路:面积等于底高,底是由两条线下标差决定,高是由两条线最短的线决定(木桶理论).假如有两个指针left和right分别指向头和尾,此时的面积是$min(a[left],a[right])(N-1)$,而且这时候的底是最长的.如果这时候的面积值并不是最大值,也就是说存在:

$Base Height > min(a_1,a_N) (N-1)$.

这种情况下由于Base一定小于(N-1),也就是说Height要比之前的大,那么,应该一定$a_1,a_N$两条线中较短的那条线,保证面积的高度可以发生改变(增大),也就是说:

  • 如果$a_1 < a_N$,问题变成在$a_2,a_N$之间查找最大面积,也就是left++;
  • 如果$a_1 > a_N$,问题变成在$a_1,a_{N-1}$之间查找最大面积,也就是right–;
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int maxArea(vector<int>& height) {
int left=0, right = height.size()-1;
int area = 0;
while(left < right){
area = max(area, min(height[left], height[right])*(right-left));
if(height[left] < height[right]) left++;
else right--;
}
return area;
}
};

时间复杂度O(N).

优化:关注自己解法存在的问题,优化方向是什么.比如说暴力破解方法,N*N,主要是因为做了一些不必要的计算,所以下一步的优化方向就是如何减少这些计算,这就需要重新审题,发现题目中的隐藏信息以及问题存在的性质.

您的支持就是我更新的最大动力!谢谢!