题目描述

给你 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,8,6,2,5,4,8,3,7] 输出：49

双指针

守住最大边 短的边向里面滑动 保存下来每次的最大值

class Solution { public int maxArea(int[] height) { int i = 0, j = height.length - 1, res = 0; while(i < j){ res = height[i] < height[j] ? Math.max(res, (j - i) * height[i++]): Math.max(res, (j - i) * height[j--]); } return res; } }

动态规划

这个方法超出时间限制 不通过 主要看思想 双层循环 计算每一个dp[i][j]的大小 所以会超时

class Solution { public int maxArea(int[] height) { int len = height.length; if(len<2 || height==null) return 0; int[][] dp = new int[len][len]; int i = 0; int j = 1; int initJ = 1; while (j < len) { while (i < len && j < len) { if (i + 1 == j) { dp[i][j] = Math.min(height[i], height[j]); } else { dp[i][j] = Math.max(dp[i][j - 1], Math.max(dp[i + 1][j], (j - i) * Math.min(height[i], height[j]))); } i++; j++; } i = 0; initJ++; j = initJ; } return dp[0][len - 1]; } }

递归

class Solution { // maxArea(i, j) where j - i == 1 = min(h[i], h[j]) // maxArea(i, j) = max( //. [(j - i) * min(h[i], h[j]), //. // We can omit one of below. //. maxArea(i+1, j), //. maxArea(i, j-1)]) int maxAreaWork(int[] height, int i, int j) { if (j - i == 1) return Math.min(height[i], height[j]); int primaryChoose = (j-i)*Math.min(height[i], height[j]); int secondaryChoose = height[i] > height[j] ? maxAreaWork(height, i, j-1) : maxAreaWork(height, i+1, j); return Math.max(primaryChoose, secondaryChoose); } public int maxArea(int[] height) { return maxAreaWork(height, 0, height.length - 1); } }