昆明网站推广8888168,想学营销策划去哪里学,桂城网站制作公司,网站制作首选 新鸿儒目录
#x1f495;1.题目
#x1f495;2.解析思路
本题思路总览
借助双指针探索规律
从规律到代码实现的转化
双指针的具体实现
代码整体流程
#x1f495;3.代码实现
#x1f495;4.完结 二十七步也能走完逆流河吗 #x1f495;1.题目 #x1f495;2.解析思路…目录
1.题目
2.解析思路
本题思路总览
借助双指针探索规律
从规律到代码实现的转化
双指针的具体实现
代码整体流程
3.代码实现
4.完结 二十七步也能走完逆流河吗 1.题目 2.解析思路 本题思路总览 力扣 11 题 “盛最多水的容器” 要求在给定的整数数组 height 中找出两条垂线使得它们与 x 轴共同构成的容器能容纳最多的水。容器的容积取决于两条垂线的距离以及两条垂线中较短的那条的高度。我们可以采用双指针的方法从数组的两端开始向中间移动指针不断更新最大容积最终找到容纳最多水的容器。 借助双指针探索规律 双指针的起始位置与移动方向 我们使用两个指针 left 和 right 分别指向数组的起始位置和结束位置。因为容器的宽度即两指针之间的距离在初始时是最大的随着指针的移动宽度会逐渐减小。我们通过移动指针来寻找可能使容器高度增加的情况从而有可能增大容器的容积。 容积的计算与指针移动规则 容器的容积计算公式为 v min(height[left], height[right]) * (right - left)其中 min(height[left], height[right]) 表示两条垂线中较短的那条的高度right - left 表示两条垂线之间的距离。为了有可能增大容积我们需要尝试改变较短的那条垂线因为移动较长的垂线不会使容器的高度增加只会让宽度减小从而使容积变小。所以当 height[left] height[right] 时我们移动左指针 left当 height[left] height[right] 时我们移动右指针 right。 从规律到代码实现的转化 既然我们知道可以通过双指针的移动来不断尝试增大容器的容积那么在代码中就可以直接使用双指针进行操作。双指针的移动规则和容积的计算逻辑与上述规律一致通过不断移动指针并更新最大容积就能找到容纳最多水的容器。 双指针的具体实现 双指针定义 left作为左指针初始时指向数组的第一个元素。 right作为右指针初始时指向数组的最后一个元素。 2. 指针移动规则 当 height[left] height[right] 时我们判断 height[left 1] 是否大于 height[left]如果是则将左指针右移一位否则为了尝试找到更高的垂线将左指针右移两位。 当 height[left] height[right] 时我们判断 height[right - 1] 是否大于 height[right]如果是则将右指针左移一位否则将右指针左移两位。 3. 终止条件 当左指针 left 大于等于右指针 right 时说明已经遍历完所有可能的组合此时终止循环。 代码整体流程 变量初始化 初始化左指针 left 为 0右指针 right 为数组的长度减 1最大容积 sum 为 0。 循环计算 在 left right 的条件下不断进行以下操作 计算当前指针所构成容器的容积 v并更新最大容积 sum。 根据 height[left] 和 height[right] 的大小关系按照上述指针移动规则移动指针。 2. 返回结果 循环结束后返回最大容积 sum。 通过以上步骤我们就可以利用双指针准确找到容纳最多水的容器 3.代码实现 class Solution {
public:int maxArea(vectorint height) {int left 0;int right height.size()-1;int sum 0;while(leftright){int v min(height[left],height[right])*(right-left);sum max(sum,v);if(height[left]height[right]){if(height[left1]height[left])left;elseleft2;}else{if(height[right-1]height[right])right--;elseright-2;}}return sum;}
}; 4.完结
