文章目录
- 1.题目
- 示例
- 提示
- 2.解答思路
- 3.实现代码
- 结果
- 4.总结
1.题目
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明:**你不能倾斜容器。
示例
提示
2.解答思路
两层for循环的做法时间会超时
因此利用双指针进行一遍遍历。
我们要清楚:
每轮向内移动短板,所有消去的状态都 不会导致面积最大值丢失
即:向内移动短板的操作是为了
- 丢弃不可能的情况(裁剪无效搜索空间),
- 保留可能的情况(保留有效搜索空间),
- 然后对所有可能的情况枚举计算(在有效搜索空间中枚举搜索)即可得出结果。
3.实现代码
class Solution {
public:
int maxArea(vector<int>& height) {
int max = 0;//最后结果
int i = 0, j = height.size()-1;
int sum = 0; // 临时存放储水量
while (i < j)
{
int a = height[i], b = height[j];
sum = (j - i) * (b > a ? a : b);//计算当下的储水量
/*若height[i]<height[j]时,
增加i. 反之,减小j
这个条件一定弄明白,这是关键。
*/
if (a < b)//逐渐缩小比较范围
{
i++;
}
else
{
j--;
}
max = (sum > max ? sum : max);
}
return max;
}
};
结果
4.总结
双指针的变化条件要找准。
双指针的一遍遍历 比 两层for循环的暴力解法快很多。
感冒好了不少了,课本的题正在做,这几天估计就会有更新啦
自信,坚持,upup~