精选50题之 11. 盛最多水的容器

布满荆棘的人生 2024-04-17 21:17 43阅读 0赞

### 腾讯精选练习（50 题）之 11. 盛最多水的容器 ###

*   *  原题目链接
     *  直接尝试
     *  题目分析
     *  解题思路
     *  代码实现
     *  写在最后

## [原题目链接][Link 1] ##

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

说明：你不能倾斜容器，且 n 的值至少为 2。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_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

## 直接尝试 ##

最直观的思路，是在所有组合中找到最大值，即暴力求解。

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

复杂度分析：

*  时间复杂度：O(n^2)；
 *  空间复杂度：O(1)，恒定常数量级。

于是乎，运行结果…  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1][]  
PS.本来还想优化，结果一看实例 1~15000 的连续数组，放弃了…

## 题目分析 ##

暴力算法完败，说明思路出现了问题，一定有其它方式。  
回到原题目，容器大小是由长度和高度决定，实际上是双变量问题。为使容积增大，无非增加长度or增加高度。由于各个位置高度其实已经给出，那么自变量可以认为是长度。  
也就是：双指针法

## 解题思路 ##

从长度最大时开始，向中间收拢，选择高度较短的一个作为高度进行求解，顺序比较，纪录最大值。

## 代码实现 ##

class Solution {
        
    public:
        int maxArea(vector<int>& height) {
        
            int area = 0, l = 0, r = height.size() - 1;
            while(l < r)
            {
        
                area = max(area, min(height[r], height[l]) * (r-l));
                if(height[l] < height[r])
                    l++;
                else
                    r--;
            }
            return area;
        }
    };

运行结果，效果显著  
![非最好结果截图][20190901131358753.png]

优化参考：8ms

class Solution {
        
    public:
        int maxArea(vector<int>& height) {
        
            int l=0;
            int h=height.size()-1;
            int max=0;
            while(l<h){
        
                int m = min(height[l],height[h])*(h-l);
                max = max>=m?max:m;
                if(height[l] > height[h]) h--;
                else l++;
            }
            return max;
        }
    };

## 写在最后 ##

周末愉快~

[Link 1]: https://leetcode-cn.com/problems/add-two-numbers/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/3dfecc9e8c784f408687f620b11de175.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/cd644d3866d54728a446bab032bfc6b9.png
[20190901131358753.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/bb4605725ec242559476ea88bfc5e63e.png