企业网站建设制作,wordpress 主题缩略图,网站建设咨询服务,互联网品牌营销服务公司题目
给定一个长度为 n 的整数数组 height 。有 n 条垂线#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
思路
双指针法#xff0c;一左le…题目
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
思路
双指针法一左left一右right。左右指针分别从两侧的边界开始记录每次以left和right为边界的容量。然后再改变其中更小的一个边界重复直到两个边界重合找到最大的一个即为答案。 当改变容器边界时改变小边界是在同时改变容器的长和高长边小了高可能变大也可能变小也可能不变对应容量也有变大变小不变的情况。如果改变大边界长变小了高肯定是不会比当前还大了容量也不会变大。双指针法枚举了可能成为最大容量的情况那些没有出现的情况通过以上推理可知会比枚举的情况小。
代码
class Solution {
public:int maxArea(vectorint height) {int ans0;int left0,right height.size()-1;while(leftright){int temp (right-left)*min(height[left],height[right]);if(tempans){anstemp;}if(height[left]height[right]){left;}else{right--;}}return ans;}
};
