1、前言

2、思路

此题可以采用暴力法求解，时间复杂度 O（n^2）。但是看到这种数组的题目，一般都会想到递归的解法，定义一个函数 dp(left, right)，left、right 初始值分别为0、length - 1。本来我们可以求开始的值，即：Math.min(height[left], height[right]) * (right - left)，然后求 left + 1 到 right 的值，在求 left 到 right - 1 的值，再算他们中最大的值。无奈最后超出内存限制，因为递归树太大了。

所以应该优化下递归结构，如果 height[left] > height[right]，那么应该保留 left，递归 left 到 right - 1 的地方；否则，保留 right，递归 left + 1 到 right 的地方。

还可以采用贪心加双指针的方法，其实上面的动态规划很像贪心，写出的代码也相似。

3、代码

public class Q11_MaxArea {

    private int max = 0;

    /**
     * 动态规划
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int n = height.length;
        dp(height, 0, n - 1);
        return max;
    }

    private void dp(int[] height, int left, int right){
        if(left >= right){
            return;
        }


        max = Math.max(max, Math.min(height[right], height[left]) * (right - left));
        if(height[left] > height[right]){
            dp(height, left, right - 1);
        }else{
            dp(height, left + 1, right);
        }
    }

    /**
     * 贪心
     * @param height
     * @return
     */
    public int maxArea2(int[] height) {
        int left = 0, right = height.length - 1, res = 0;

        while (left < right){
            res = height[left] < height[right] ?
                    Math.max(res, (right - left) * height[left++]) :
                    Math.max(res, (right - left) * height[right--]);
        }

        return res;
    }

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