盛最多水的容器

题目描述

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标
内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条
线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器，且 n 的
值至少为 2。

leecode截图

思路

一般遇到这种题,我们可能会有好几种思路,第一种可能直接暴力法,直接算出所有可能性,得
出最大值,但是我们做的是算法题,暴力法往往不是最优解,而且对我们算法能力也不会有什
么提高.这道题是找出最大面积,其实看到这种问题,我们第一思路就应该是指针.
利用双指针来做,左右指针,每次数值小的往里移动,直到指针相遇,结果就出来了

题解代码

public class MaxArea {
    public static void main(String[] args) {
        int[] a = new int[]{1,8,6,2,5,4,8,3,7};
        int i = new MaxArea().maxArea(a);
        System.out.println(i);
    }

    public int maxArea(int[] height) {
        if (height.length == 2) {
            return Math.min(height[0],height[1]);
        }
        int left = 0;
        int right = height.length - 1;
        int maxArea = (right - left) * Math.min(height[left], height[right]);

        while (left < right) {
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
            maxArea = Math.max(maxArea, (right - left) * Math.min(height[left], height[right]));
        }
        return maxArea;
    }
}