科技厅,哪家公司做推广优化好,大连市城乡建设局网站,wordpress 文章摘取一、题目描述 11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明第 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_;
}
