前言
无(doge)
最大盛水
题目意思很简单,我们有要以数组元素为高数组下标差为底创建一个桶然后我们需要返回容量最大的桶的容量即可.
暴力解决
空间复杂度O(1)时间复杂度O(n2)
先来个思路简单的,我们只需要从头到尾的固定一个桶的一边然后向后寻找桶的另一边此时当桶的值大于ret时就可以将其值作为ret的值了.
代码如下.
class Solution { public: //方法:从头到尾进行比较最后将最大值返回即可. int maxArea(vector<int>& height) { int n = height.size(); int ret = 0; for(int j =0;j < n; j++) { if(height[j]*(n-j)<ret)//以j为桶一边的值最大其实就是height[j]*(n-j)了所以当ret>这个值时也就没必要进行下面的循环比较了. continue; for(int i= j+1;i<n;i++) { int max = height[j]; int min = height[i]; if(min>max) { swap(min,max); } if(min*(i-j)>ret) { ret = min*(i-j); } } } return ret; } };
双指针法
空间复杂度O(1)时间复杂度O(n)
这个思路其实也是非常简单的.
我们需要知道的是,桶容积随着左右指针变化时的规律
我们知道桶容积是 (两边最低高度) 乘于 (下边下标的相减值) 的乘积.
所以当两边高度中的最小值不变的时候去挪动最大值的那只指针时桶的容积不可能会增加(因为下标的相减值变低了)
所以我们只需要挪动最小值那个指针使其改变即可.
代码如下
class Solution { public: int maxArea(vector<int>& height) { int left = 0; int right = height.size()-1; int ret = 0;//返回值 while(left<right) { int area = min(height[right],height[left])*(right-left);//当前right和left对应的桶容积 ret = max(area,ret); //下面两个if都是为了挪动最小值那个的指针. if(min(height[right],height[left])==height[right]) { right--; } else if(min(height[right],height[left])==height[left]) { left++; } } return ret; } };
