Leecode11. 盛最多水的容器——Leecode大厂热题100道系列

悠悠 2022-09-14 01:59 102阅读 0赞

## 我是小张同学，立志用最简洁的代码做最高效的表达 ##

--------------------

以下是我个人做的题解，每个题都尽量囊括了所有解法，并做到了最优解，欢迎大家收藏！留言！

#### 传送门——>[**Leecode大厂热题100道系列题解**][Leecode_100] ####

--------------------

### 问题描述 ###

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

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

> 提示：  
> n == height.length  
> 2 <= n <= 10^5  
> 0 <= height\[i\] <= 10^4

--------------------

### 思路：双指针法 ###

面积取决于短板。

①  因此即使长板往内移动时遇到更长的板，矩形的面积也不会改变；遇到更短的板时，面积会变小。  
②  因此想要面积变大，只能让短板往内移动(因为移动方向固定了)，当然也有可能让面积变得更小，但只有这样才存在让面积变大的可能性

--------------------

class Solution {
        
    public:
        int maxArea(vector<int>& height) {
        
            int maxArea = 0, i = 0, j = height.size();
            while(i < j) {
        
                maxArea = max(maxArea, (j-i) * min(height[i], height[j]));
                height[i] < height[j] ? i++ : j--;
            }
            return maxArea;
        }
    };

[Leecode_100]: https://zhanglong.blog.csdn.net/article/details/120545161