盛水问题

问题描述

给你 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.由问题的描述我们可以得知，两条垂直于x轴的线，与x轴构成了一个容器，由于水是流动，保持水平面对其，所以以x轴为底的话，高就是两条垂直线的最小边 2.我们先固定一条边不动，再遍历另一条边，这样的时间复杂度比较高o(n的平方) 3.面积公式为Math.min(height(i),height(j))*(j-i)

代码：

class Solution { public int maxArea(int[] height) { int n=height.length; int maxSize=0; int size = 0; if(n<2) return 0; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { size = ((j - i) * Math.min(height[i] ,height[j])); if (maxSize < size) maxSize = size; } } return maxSize; } }

运行速度和内存消耗：

解答成功: 执行耗时:728 ms,击败了7.62% 的Java用户 内存消耗:39.7 MB,击败了16.14% 的Java用户

使用双指针解法

双指针解法

为什么选择双指针

双指针代表的是 可以作为容器边界的所有位置的范围。在一开始，双指针指向数组的左右边界，表示 数组中所有的位置都可以作为容器的边界，因为我们还没有进行过任何尝试。在这之后，我们每次将 对应的数字较小的那个指针 往 另一个指针 的方向移动一个位置，就表示我们认为 这个指针不可能再作为容器的边界了

代码：

class Solution { public int maxArea(int[] height) { int s=0,e=height.length-1; int maxArea=0; while(s<e) { int area = (e-s)*Math.min(height[s],height[e]); maxArea=Math.max(area,maxArea); if(height[s]<=height[e]) s++; else e--; } return maxArea; } }

时间复杂度是O(n)

运行时间及内存消耗

执行耗时:4 ms,击败了68.15% 的Java用户 内存消耗:40.1 MB,击败了11.92% 的Java用户