企业官网响应式网站,企业网站定制多少钱,外贸网站做啥,个人注册公司流程和费用一、题目解析 分析这个题目不难得出一个容积公式 二、算法原理
解法一#xff1a;暴力枚举#xff08;超时#xff09;
套用上述的容积公式#xff0c;使用两个for循环来枚举出所有可能的情况#xff0c;再挑出最大值即可#xff0c;但是这种写法会超时#xff0c;导致…一、题目解析 分析这个题目不难得出一个容积公式 二、算法原理
解法一暴力枚举超时
套用上述的容积公式使用两个for循环来枚举出所有可能的情况再挑出最大值即可但是这种写法会超时导致不通过。时间复杂度是O(n^2)
class Solution {
public:int maxArea(vectorint height) {int n height.size();int ret 0; for (int i 0; i n; i) {for (int j i 1; j n; j) {ret max(ret, min(height[i], height[j]) * (j - i));}}return ret;}
};
可以自己去尝试一下。
解法二双指针
设两个指针leftright分别为这个容器的左边界和右边界根据容积公式可得
v min( height[right], height[left]) * (right - left)
从题目中的测试用例中选取一段进行分析如下
所以我们可以得出结论用较小的数向内枚举的话容积肯定是在减小的所以较小的数我们就可以不用向后枚举了直接跳过用较大的数向后枚举就行。
最后选出容积最大值就行了。 时间复杂度是O(n)。
三、代码编写
class Solution {
public:int maxArea(vectorint height) {int left 0, right height.size() - 1, ret 0;while(left right){int v min(height[left],height[right]) * (right - left);ret max(ret, v);if(height[left] height[right]){left;}else {right--;}}return ret;}
};
