【算法|双指针系列No.4】leetcode11. 盛最多水的容器

个人主页：兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

点解直接跳转到该题目

1️⃣题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 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

注意：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

2️⃣算法分析

通过不断地调整较短的边界来寻找可能的最大容量。因为容器的容量受限于较短的边界，所以选择移动较短的边界可以增加容器的高度，有可能得到更大的容量。通过不断缩小指针之间的宽度，直到指针重合，即可得到最大容量。

容器容量：v = s * h，由于我们这里不断移动两个“指针”，所以 s 是不断变小的，那么问题来了，我们要移动哪个指针呢（是向右移动左指针的，还是向左移动右指针呢？），我们要知道无论我们移动哪一个指针容器的 s 都是减小的，此时如果要使得容器容量增大，我们需要移动指针指向的值较小的那个指针。举个例子（1，9），我们此时就需要向右移动左指针了，因为我们只有移动左指针才有可能使得容器的容器容量变大（即通过增加h的方式）。
即：

if(height[l] < height[r]) l++;
else r--; 
1
2

3️⃣代码编写

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0,r = height.size() - 1,ret = 0;
        while(l < r)
        {
            int v = (r - l) * min(height[l],height[r]);
            ret = max(v,ret);
            if(height[l] < height[r]) l++;
            else r--; 
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14