【Leetcode面试常见题目题解】4. 盛最多水的容器

题目描述

本文是LC第11题：盛最多水的容器。
题目描述如下：

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

限制

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

示例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

解题思路

• 暴力解法
• 双指针
  有句话：你的能力取决于你的短板。这句话的来源正是水桶问题，一个有一面短板的水桶最多的盛水量由短板的高度决定。（水桶上下半径是确定的）
  对于本题，容器的盛水量取决于两个因素——容器的底和容器较短的那条高。 容器高度较大的一侧的移动只会造成容器盛水量减小，所以应当移动高度较小一侧的指针，并继续遍历，直至两指针相遇 。

假设有左指针 left 和右指针 right ，且 left 指向的值小于 right 的值，如何移动双指针才能保证最大的盛水量被遍历到，假如我们将右指针左移，则右指针左移后的值和左指针指向的值相比有三种情况：

右指针指向的值 > 左指针（指向的值），容器的高取决于左指针，但是底变短了，所以容器盛水量一定变小；
右指针指向的值 == 左指针（指向的值），容器的高取决于左指针，但是底变短了，所以容器盛水量一定变小；
右指针指向的值 < 左指针（指向的值），容器的高取决于右指针，但是右指针小于左指针，且底也变短了，所以容量盛水量一定变小了.

代码

双指针解法

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0; // 注意水位有可能是0，因此最小面积为0
        int i = 0; // 左指针
        int j = height.size() - 1; // 右指针
            
        while ( i < j ) { // 循环直到左右指针相遇
            maxArea = max(maxArea, (j-i)*min(height[i], height[j]));  // 记录最大面积，与当前i,j围成的面积比较
            if ( height[i] < height[j]) { // 移动指向较小值的指针
            	++i;
            } else { 
            	--j;
            }
    
        }
        return maxArea;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

双指针优化解法：上述第一版代码其实是不断移动较小的指针，然后计算当前围成的面积，当当前围成的面积 > 最大面积时，更新最大面积，然后继续直到 i >= j。
因此也可以采用如下这种代码写法，语义为 “记录下当前较小值，移动指向较小值的那个指针，直到指针指向的值 > 记录的较小值”，其实就是一次性多跳几个比当前值还小的的值，省去了几次计算面积的开销。
但这样的写法不建议使用，代码虽然优化了，但优化力度甚至可以忽略。
在写算法实现的时候，一定要记住：有思路，有最简单易懂的实现可以解决问题的时候，不要再去花过多的时间绞尽脑汁的在一些优化度不高的点上优化。因为即便写出了如下的代码，别人也未必能一眼看懂。而且还消耗了自己的时间。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0; // 注意水位有可能是0，因此最小面积为0
        int i = 0; // 左指针
        int j = height.size() - 1; // 右指针
            
        while (i < j) { // 循环直到左右指针相遇
            int h = min (height[i] , height[j]); // 记录下当前较小值
            maxArea = max (maxArea, (j-i) * h); 
            // h 是 height[i] , height[j] 中的一个，所以以下两个循环只执行其中一个
            while(i < j && height[i] <= h) ++i; 
            while(i < j && height[j] <= h) --j;
        }
        return maxArea;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

补上这段代码实际做的事：