等级:中等
一、题目
给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 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
示例 3:
输入:height = [4,3,2,1,4]
输出:16
示例 4:
输入:height = [1,2,1]
输出:2
提示
:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
二、代码及思路
这道题要使用双指针进行。 之前有使用双指针做的题,不懂得可以会看一下这几篇双指针的题(6 移除元素和7 有序数组的平方)
定义两个指针,分别指向开始和结尾。此时的width是max的。我们在进行指针移动的时候会导致width减小,此时根据Area公式,如果要Area增大,那就只能是height增加,我们通过两个指针所处位置的值进行比较,哪个小就移动哪个指针。
class Solution { public int maxArea(int[] height) { int width = height.length; int left = 0, right = width - 1; int res = 0; while(left < right){ width = right - left; int h = Math.min(height[left], height[right]); res = Math.max(res, width * h); if(height[left] > height[right]){ right--; }else{ left++; } } return res; } }