网站建站助手,重庆工信部网站,wordpress 4.8.2中文,wordpress前台加速题目
给定一个长度为 n 的整数数组 height 。有 n 条垂线#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明#xff1a;你不能倾斜容器。…题目
给定一个长度为 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 思路
题目给定一个数组让求最大容量有以下两种方法
一、暴力枚举 从下标0开始把所有情况全部算出来求最大及其原始暴力的方法作为一个学习算法和编程的人首先排除此方法。
二、双指针
此类型题目可以理解为日常生活中所说的木桶效应一个木桶能装多少水是由最短的那块板子来决定的同样在计算容积时高是由最短的那个数来决定的而想要从数组中找出最优解枚举是不可缺少的但要尽可能的控制枚举的次数从而降低代码的时间复杂度。
用h表示高w表示宽 从中间随机截取一段来举例[6,2,5,4]首先可以算出体积为3*412现在假设拿4依次根其他几个数作枚举w无疑是在减小的那么现在会出现两种情况
但只要仔细观察就会发现无论哪种情况总容量都是在减少的。
1.h比4小和刚开始比h减小了w也减小了容量无疑也减小了。
2.h比4大那高度还得是4所以和刚开始比h不变w减小容积量在减小。
所以当在一个区间内选最左和最右两个数算出容积之后两个数中小的那个数已经完全没有必要再去向内进行枚举了因为无论怎么枚举容量都是变小的。此时4可以直接不考虑了。
我们可以知道容量是受宽和高的影响的而我们需要找出的就是一个宽和高都相对较高的值结合上面的分析所以为了加快效率两个指针一个在前一个在后同时由外向内进行遍历可以大大节约时间那边小直接向内移动那边然后计算容量这样就可以用O(n)的时间复杂度来找出最大容量了。 扩大到整个数组最左最右计算完直接干掉1向右移继续找如果比之前算出来的都大就更新max。
题解
class Solution {
public:int maxArea(vectorint height) {int left0,rightheight.size()-1;int max0,h0,w0;while(leftright){wright-left;if(height[left]height[right]) hheight[left];else hheight[right--];if(w*hmax) maxw*h;}return max;}
};
