免费软件安装网站,上海网站推广价格,商城型网站开发网站建设,猎豹加速器盛水最多的容器
#xff08;1#xff09;暴力解法 算法思路#xff1a;我们枚举出所有的容器大小#xff0c;取最大值即可。 容器容积的计算方式#xff1a; 设两指针 i , j #xff0c;分别指向水槽板的最左端以及最右端#xff0c;此时容器的宽度为 j - i 。由于容器… 盛水最多的容器
1暴力解法 算法思路我们枚举出所有的容器大小取最大值即可。 容器容积的计算方式 设两指针 i , j 分别指向水槽板的最左端以及最右端此时容器的宽度为 j - i 。由于容器的高度由两板中的较短的板决定因此可得容积公式 v (j - i) * min( height[i] , height[j] );
class Solution {
public:int maxArea(vectorint height) {int nheight.size();int ret0;//枚举出所有的容器大小for(int i0;in;i){for(int ji1;jn;j){//计算当前的容器容量int v(j-i)*(min(height[i],height[j]));retmax(ret,v);//取最大容量的容器}}return ret;}
};当然由于两次遍历数组所以时间复杂度为O(N2)会超时。 2对撞指针 算法思路我们设置两个指针left、right分别指向容器的两个端点因为这里的是数组数组在内存中的储存是连续的而且数组是通过它们的下表访问所有我们可以把数组下标看成是指针进行操作不断修改左右的端点来获得容器的最大容量。 容器的左边界为 height[left] 右边界为 height[right] 。 我们假设「左边边界」小于「右边边界」。 水的容积会有如下变化形式 首先容器的宽度⼀定变小。由于左边界较小决定了水的高度。如果改变左边界新的水面高度不确定但是⼀定不会超过右边的柱子高度因此容器的容积可能会增大或者减小。 但是如果改变右边界无论右边界移动到哪⾥新的水面的高度⼀定不会超过左边界也就是现在左边界的所在的水面高度但是由于容器的宽度减小因此容器的容积一定会变小。 综上我们不断选取左右两个边界中的较大边界以保留当下的最有解不断的 left 或right–直到left和right相遇。
class Solution {
public:int maxArea(vectorint height) {int left0;int rightheight.size()-1;int ret0;//循环条件为右边界大于左边界while(leftright){//计算当前容器的容量int v(right-left)*(min(height[left],height[right]));retmax(v,ret);//不断更新容器的最大容量if(height[left]height[right]) right--;//不断更新左右高度else left; //保留高的舍弃较矮的高}return ret;}
};时间复杂度O(N)
和为s的两个数字 和两数之和不同的是该数组中的元素是有序的而且使用暴力解法会超时。
1对撞指针
这里有三种情况 当 nums[left] nums[right] target时说明找到结果记录结果并且返回 当 nums[left] nums[right] target 时此时 nums[right] 相当于是 nums[left] 能碰到的最大值。如果此时不符合要求说明我们需要增加这两个数之和所以我们让left再取更大的数以来靠近我们的目标和。 当 nums[left] nums[right] target 时说明我们所取的两数较大所以我们应该减小这两个数之和让right–以此使得两数的总和变小以此来靠近我们的目标和。不断比较下⼀组数据直至两数和和目标和相等。
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int left0;int rightnums.size()-1;while(leftright){//如果两数和等于目标值直接返回if(nums[left]nums[right]target){return {nums[left],nums[right]};}//如果两数和大于目标值right--else if(nums[left]nums[right]target){right--;}//如果两数和小于目标值left else{left;}}//照顾编译器返回一个不存在的数组return {-1141514};}
};时间复杂度O(N)
