LeetCode11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例：

输入： [1,8,6,2,5,4,8,3,7]
输出： 49
解释： 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此环境下，容器可以大概容纳水（表示为蓝色部分）的最大值为 49。
提示

n == height.length
2 <= n <=                                    1                                   0                            5                                       10^5                  105
0 <= height <=                                    1                                   0                            4                                       10^4                  104
解答

• 这道题刷到的时间感觉很有意思就分享了出来
  
• 看到第一眼想到的办理方法肯定是暴力法，两个for循环，但一看n的范围肯定会超时，就想了一下能不能用双指针办理，因为这题的标签有双指针嘛，但要想让两边的指针移动就要有一个条件。如今我们就要分析这个条件是什么。标题要求的是容纳水的容量最大，那这个条件按理来说应该和水的容量有关，那我们求一下容器的容量
  假设：i为左指针，j为右指针，res为容器容量
                                           r                            e                            s                            =                            (                            j                            −                            i                            )                            ∗                            m                            i                            n                            (                            h                            e                            i                            g                            h                            t                            [                            i                            ]                            ,                            h                            e                            i                            g                            h                            t                            [                            j                            ]                            )                                  res=(j - i) * min(height,height[j])                     res=(j−i)∗min(height,height[j]) 看起来这个面积的厘革不确定，但我们细致分析一下
  
• 假如将短板向内移动，min(height,height[j])可能变大，因为长板没有动所以水槽的短板可能变大
  
• 假如将长板向内移动，min(height,height[j])稳定或变小，因为移动了长板，假如移动后长板依然比短板高，那么min(height,height[j])稳定，假如移动后长板比短板低，那么min(height,height[j])会变小
  
• 因此只有将短板向内移动，水槽容量才可能变大，所以我们应该运用贪心的头脑，每次移动都向内移动短板，使得容量有增大的趋势，如许我们就分析完了。
  

1. class Solution {
2.     public int maxArea(int[] height) {
3.         int i = 0, j = height.length - 1, res = 0;
4.         while(i != j){
5.             res = height[i] > height[j] ?
6.                 Math.max(res,(j - i) * height[j--]):
7.                 Math.max(res,(j - i) * height[i++]);
8.         }
9.         return res;
10.     }
11. }

复制代码

以后会以java语言来写算法的代码
不懂的同学可以在评论区留言或私信

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。