- 难度: 中等
- 考察: 数组
- 来源: https://leetcode-cn.com/problems/container-with-most-water/description/
- 题解: https://github.com/azl397985856/leetcode/blob/master/problems/11.container-with-most-water.md
- 题解: https://github.com/MisterBooo/LeetCodeAnimation/blob/master/0011-maxArea/Article/0011-maxArea.md
题目
给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明:你不能倾斜容器,且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例:
1 | 输入:[1,8,6,2,5,4,8,3,7] |
思路
暴力法
容器可以容纳水的容量=两条垂直线中最短的那条*两条线之间的距离 现在的情况是,有很多条线,让你计算两两之间能装的最多的水,其实暴力法之间就能解决这个问题,但是它的时间复杂度也达到了O(n^2)
双指针法
思路:使用两个指针(resource和last)分别指向数组的第一个元素和最后一个元素,然后我们计算这两条“线”之间能容纳的水的容量,并更新最大容量(初始值为0);接着我们需要将指向元素值小的那个指针前移一步,然后重复上面的步骤,直到resource = last循环截止。
关键点
- 木桶原理,容量取决于短的木板
复杂度
- 时间复杂度:O(N)
- 空间复杂度:O(N)
代码
暴力法
1 | func maxArea(height []int) int { |
双指针法
1 | func maxArea(height []int) int { |