盛最多水的容器

题目链接

盛最多水的容器

题目描述

注意

• 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水
• 不能倾斜容器

解答思路

• 最初看到这道题感觉有一定的规律，但是想了比较久也没想出来规律是什么，最终只想到对于任意一个位置，其盛最多水的结果有一个临界点，那就是其肯定是和前面坐标中最高点及最高点之前的坐标组成最大面积，最终写出来后耗时2000+ms，预料之内时间复杂度很差
• 参照题解使用双指针的思路完成此题，其思想是：左右指针分别指向左右边界，计算左右指针指向的坐标的面积，判断其是否是最大面积，判断后，移动左右指针当中对应高度更低的指针，再次计算面积，以此类推…遍历完成后的最大面积就是盛最多水的容器

代码

方法一：

class Solution {
    public int maxArea(int[] height) {
        int res = 0, left = 0, right = height.length - 1;
        while (left < right) {
            int area = 0;
            if (height[left] < height[right]) {
                area = height[left] * (right - left);
                left++;
            } else {
                area = height[right] * (right - left);
                right--;
            }
            res = Math.max(area, res);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

关键点

• 想到双指针解决此题