【腾讯精选练习 50 题】15—盛最多水的容器【中等】

旧城等待， 2022-10-22 02:47 277阅读 0赞

## 题目链接 ##

[11. 盛最多水的容器【中等】][11.]

## 题目简介 ##

给你 `n` 个非负整数 `a1，a2，...，an，`每个数代表坐标中的一个点 (i, ai) 。在坐标内画 `n` 条垂直线，垂直线 `i` 的两个端点分别为 `(i, ai)` 和 `(i, 0)` 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

**说明**：你不能倾斜容器。

**实例一：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]

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

## 题目解析 ##

*  简单来说，就是给定两个坐标 `i` 和 `j`，让你求 `Math.,min(height[j], height[i]) * (j - i)` 的最大值
 *  我们可以使用双指针来做
    
     *  我们可以发现，对于 `j - i` 始终在缩小的，所以，我们必须要提高 `下一步的高度`
     *  我们并不知道下一个高度是大的还是小的，所以，我们可以假设
        
         *  假设 `下一个高度` 小于 `当前小的高度`：那么下一个 `存水的值` 取 `最大` 和 `最小` 没有变化
         *  假设 `下一个高度` 大于 `当前大的高度`：那么下一个 `存水的值` 取 `最大` 大于 `最小`
         *  假设 `下一个高度` 在 `当前小` 和 `当前大` 之间，那么下一个 `存水的值` 取 `最大` 大于 `最小`
         *  综上所述，我们每一次移动最短的一方，即可搜索到最大值

## 题目代码 ##

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

[11.]: https://leetcode-cn.com/problems/container-with-most-water/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20221022/26ca2021aae443d6b19881ba7db05223.png