币圈小鱼儿
【LBank交易所是哪国的】双指针求盛最多水的容器
来源： 数据结构和算法-山大王 wld
问题描述
给你 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
暴力求解
这种题最容易想到的是暴力求解，就是计算每两个柱子所围成的面积，把所有的都计算一遍，然后保留最大值即可。但暴力求解效率一般都不高，我们看看即可，代码如下
1public int maxArea(int[] height) { 2 int maxarea = 0; 3 int area = 0; 4 int length = height.length; 5 for (int i = 0; i < length - 1; i++) { 6 for (int j = i + 1; j < length; j++) { 7 area = Math.min(height[i], height[j]) * (j - i); 8 maxarea = Math.max(maxarea, area); 9 } 10 } 11 return maxarea; 12}
双指针求解
根据木桶原理，桶的容量是由最短的木板决定的，所以这里矩形的高度也是由最矮的柱子所决定的。我们可以使用两个指针，一个 left 指向左边的柱子，以他的高为矩形的高度，然后从最右边开始往左扫描，找到比 left 柱子高的为止（如果没找到，那么矩形的宽度就是 0）。计算矩形面积之后，left 再往右移一位，再以同样的方式继续查找……。
比如下面的图中计算以第 1 个柱子的高度为矩形的高度，因为高度一定，要想使矩形的面积最大，就只能是矩形的宽度最大，所以这里从数组的最后面开始找，找到一个比 3 大或者等于 3 的值即可，如果没找到那么宽度就是 0。
我们查找的时候为了防止遗漏，不光从前面开始找，而且还要从后面开始找，需要两遍查找，代码如下
1public int maxArea(int[] height) { 2 int maxarea = 0, left = 0, length = height.length; 3 int area; 4 int right; 5 // 从前面开始找 6 while (left < length) { 7 right = length - 1; 8 while (right > left) { 9 if (height[right] < height[left]) { 10 right--; 11 } else { 12 break; 13 } 14 } 15 // 计算矩形的面积 16 area = height[left] * (right - left); 17 // 保存计算过的最大的面积 18 maxarea = Math.max(maxarea, area); 19 left++; 20 } 21 // 从后面开始找，和上面类似 22 right = length - 1; 23 while (right > 0) { 24 left = 0; 25 while (right > left) { 26 if (height[right] > height[left]) { 27 left++; 28 } else { 29 break; 30 } 31 } 32 area = height[right] * (right - left); 33 maxarea = Math.max(maxarea, area); 34 right--; 35 } 36 return maxarea; 37}
双指针优化
上面的代码我们两个方向都要查找，是不是感觉有点麻烦，我们再认真看下这个图
比如我们以 3 为矩形的高度，查找矩形宽度的时候从最右边开始往左找，找到比 3 大的为止，这里找到了 4，那么柱子 3 到柱子 4 中间所围成的矩形高度就是柱子 3 的高度。如果我们从右边开始找的时候是小于 3 的，比如这里是 2，那么我们这里是不是找到了以 2 为高度的矩形的最大面积。也就是相当于我们可以把从前往后和从后往前找合并为一个，所以这里代码就非常简洁了，我们来看下
1public int maxArea(int[] height) { 2 int maxarea = 0, left = 0, right = height.length - 1; 3 int area = 0; 4 while (left < right) { 5 // 计算面积，面积等于宽*高，宽就是 left 和 right 之间的距离，高就是 6 //left 和 right 所对应的最低高度 7 area = Math.min(height[left], height[right]) * (right - left); 8 // 保存计算过的最大的面积 9 maxarea = Math.max(maxarea, area); 10 // 柱子矮的往中间靠 11 if (height[left] < height[right]) 12 left++; 13 else 14 right--; 15 } 16 return maxarea; 17}
这题基本上没什么难度，主要考察对双指针的使用。
- 免责声明
- 世链财经作为开放的信息发布平台，所有资讯仅代表作者个人观点，与世链财经无关。如文章、图片、音频或视频出现侵权、违规及其他不当言论，请提供相关材料，发送到：2785592653@qq.com。
- 风险提示：本站所提供的资讯不代表任何投资暗示。投资有风险，入市须谨慎。
- 世链粉丝群：提供最新热点新闻，空投糖果、红包等福利，微信：juu3644。
