LeetCode第十一题-可以装最多水的容器

Container With Most Water

问题简介:通过一个给定数组,找出最大的矩形面积

问题详解:给定一个数组,包含n个非负整数a1,a2,…,an,其中每个表示坐标(i,ai)处的点,绘制n条垂直线,使得线i的两个端点位于(i,ai)和(i,0),找到两条线,它们与x轴一起形成一个矩形,这样矩形就含有最大的面积

注意:数组至少有两个数字

举例:

输入: [1,8,6,2,5,4,8,3,7]

输出: 49

解法一:双层遍历笨方法

复杂度分析:

空间复杂度:O(n2) - 双层遍历

时间复杂度:O(1) - 定义空间是有限次数的

解法二:Two Pointer Approach

数组最左端和最右端开始,缩小更小的一段,逐渐减少来寻找最大面积

复杂度分析:

空间复杂度:O(n) - 遍历一次数组

时间复杂度:O(1) - 定义有限空间

小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海

原文地址:https://www.cnblogs.com/lalalaczq/p/10719858.html