[LeetCode系列] 11.盛最多水的容器

219 阅读4分钟

上一篇文章向大家介绍了用于提高元素查找速率的双指针法,本文将再次利用双指针解决leetcoed问题,帮助大家更好地理解和巩固双指针用法,具体双指针法的讲解可移步[LeetCode刷题系列]15.三数之和

1.题目描述

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

说明:你不能倾斜容器,且 n 的值至少为 2。

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

示例:

输入: [1,8,6,2,5,4,8,3,7]

输出: 49

2.题目分析

将一维数组放在坐标轴上,数组中每个元素的值即为柱子的高度。从图中可以看到,坐标轴上排列着高低不一的柱子,不同高度的柱子之间所围成的面积大小,就是构成容器可容纳的水的多少。可是柱子的高度不是有序排列的,这就导致了两根高度更高的柱子,可能距离更近,所围成的面积也可能更小。

两根柱子之间的面积计算:

  1. 首先找到两根柱子之间较短的一根,作为矩形的一条边

h = min{height i, height j}

  1. 两根柱子之间的距离作为矩形的另一条边

width = j - i

  1. 矩形面积等于两边相乘。

area = h * width

Ⅰ.暴力解法

为了找到两根柱子,使其所围成面积最大,我们可以通过暴力法嵌套循环,找出所有可能的柱子的组合,计算其面积,并找到最大面积,时间复杂度为O(n^2).

  • 该方法代码如下:
class Solution {
public:
    int maxArea(vector<int>& height) {
        int max_area = 0;
        for(int i = 0; i < height.size()-1;++i){
            for(int j = i+1; j < height.size();++j){
                int min_height = height[i]<height[j]?height[i]:height[j]; 
                int area = min_height*(j-i);
                max_area = area>max_area?area:max_area; 
            }
        }
        return max_area;
    }
};

注意:

对第一层循环来说 i 的上边界是height.size()-1.

对第二层循环来说 j 的下边界是i+1.

Ⅱ.双指针法

在暴力解法中,每固定一根主柱子,就要遍历剩下的所有柱子,造成了大量元素的多次重复访问。那么我们有没有办法只扫描一次数组,就可以找到最大的面积呢?让我们来看看双指针法是怎么做的。

最开始的时候,如果我们用指针i和j指向最两端的柱子,此时两根柱子之间的距离就是最大的,即我们所求矩形面积的宽度(width)为最大。

但是位于最两端的柱子高度不一定是最高的,所以它们组成矩形的面积也就不一定是最大的。因此我们依然需要继续遍历整个数组,这时我们将指向数组两端的指针慢慢往里面收敛,直到找到面积最大值。

对于最两端的柱子,他们之间的宽度已经是最宽了。于是在收敛的过程中,如果遇到的高度比两端的柱子更低的话,由于组成的宽度更短,所以面积必定更小,我们就可以直接跳过,不予考虑。我们只需要考虑收敛时出现的那些高度更高的柱子。

该方法在双指针向中间收敛的过程中,对数组中的每个元素只访问了一次,因此时间复杂度为O(n).

3.手绘讲解

代码实现

#include<iostream>
#include<vector>
using namespace std;

int maxArea(vector<int>&);

int main()
{
  vector<int> test = { 1,8,6,2,5,4,8,3,7 };
  int max = maxArea(test);
  cout << "max area is: " << max << endl;
  return 0;
}

int maxArea(vector<int>& height)
{
  int i = 0;
  int j = height.size() - 1;
  int max_area = 0;
  while (i < j) {
    int min_height = height[i] < height[j] ? height[i] : height[j];
    int area = min_height * (j - i);
    cout << "now:" << area << endl;
    max_area = area > max_area ? area : max_area;
    while (height[i] <= min_height && i < j) ++i;
    while (height[j] <= min_height && i < j) --j;
  }
  return max_area;
}

高票回答

  • C++实现:

  • Java实现:

  • Python实现:

如果你喜欢我的文章,欢迎扫描下方二维码关注我的公众号《小R在编程》了解更多LeetCode题解思路和算法知识!