一、题目描述
11. 盛最多水的容器
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。
找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
二、题目解析
这题如果使用暴力枚举,会发现leetcode上显示超时,我们学习算法,目的就是掌握更多优秀的算法,所以暴力枚举直接摒弃掉。下面讲解时间复杂度为O(N)的双指针优秀算法:
我们首先明确一个规律:
以示例一为例,我们直接定义数组最左边为左值,数组的最右边为右值,最左边是1,保持最左边不动,然后移动最右边,会发现任何一个面积都比之前最右边的小,因为面积是由长度和高决定的,但高度不变或者变小,同样变化的还有长度,长度一定是变小的,所以左值直接摒弃。
总体思路就是先找两边高度的小值,并计算当前最大值然后摒弃最小值,缩小数组范围,继续遍历,直到left和right指针相遇,因此该算法的时间复杂度就是O(N)!
三、原码
int maxArea(int* height, int heightSize) {//还是利用快慢指针的算法 int left = 0;int right = heightSize - 1;int minh = 0;int maxArea_ = 0;while(left < right){int flag = 0;//在循环体里的变量尽量都要在循环里面重定义!!!if(height[left] <= height[right]){minh = height[left];flag = -1;}elseminh = height[right];int Area = minh * (right - left);if(maxArea_ < Area)maxArea_ = Area;if(flag == 0)right--;elseleft++;}return maxArea_;
}