网站规划有哪些内容,商贸行业网站建设,东莞百度推广优化排名,不建网站网络营销怎么做#x1f3e0;关于专栏#xff1a;专栏用于记录LeetCode中Hot100专题的所有题目 #x1f3af;每日努力一点点#xff0c;技术变化看得见 题目转载
题目描述
#x1f512;link-题目跳转链接 给定一个长度为 n 的整数数组 height 。有 n 条垂线#xff0c;第 i 条线的… 关于专栏专栏用于记录LeetCode中Hot100专题的所有题目 每日努力一点点技术变化看得见 题目转载
题目描述
link-题目跳转链接 给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
⚡说明你不能倾斜容器。
题目示例 示例 1: 输入[1,8,6,2,5,4,8,3,7] 输出49 解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。 示例 2: 输入height [1,1] 输出1 题目提示
● n height.length ● 2 2 2 n 1 0 5 10^5 105 ● 0 0 0 height[i] 1 0 4 10^4 104
解题思路及代码
暴力枚举法
既然要求两条线构成的最大容积那就计算这些线两两构成的容积大小以得到最大的容积。这个方法只需要两层for循环即可算法复杂度为 O ( N 2 ) O(N^2) O(N2)。但这个算法的时间复杂度过高最终会导致超时。
tips这里计算容积时使用的是高度×底部宽度。容器的高度取决于所有高度中较小的那一个。
class Solution {
public:int maxArea(vectorint height) {int maxCap 0;for(int i 0; i height.size(); i){for(int j i 1; j height.size(); j){int capacity min(height[i], height[j]) * (j - i);maxCap max(maxCap, capacity);}}return maxCap;}
};双指针法
若定义两个变量left0rightheight.size()-1则可以得到由最左和最右两条线所构成的容积即min(height[left], height[right]) * (right - left)。不管是left或right向内移动一格宽度均会变小故此时应当让height[left]和height[right]中小的那一个向内移动因为宽度减小需要高度增加来补充而当前高度受限于height[left]和height[right]中小的那一个若小的线不发生改变而缩小宽度则容积只会变小故每次只要将小的那一边向内移动即可。
下面通过示例1[1,8,6,2,5,4,8,3,7]执行过程图演示上述算法描述
class Solution {
public:int maxArea(vectorint height) {int maxCap 0;int left 0, right height.size() - 1;while(left right){int capacity min(height[left], height[right]) * (right - left);maxCap max(maxCap, capacity);if(height[left] height[right]) --right;else left;}return maxCap;}
};刷题使我快乐 文章如有错误请私信或在下方留言
