LeetCode 题解——Container With Most Water

发表于 | 分类于 | 阅读次数:
字数统计: 349 字

LeetCode 题解——Container With Most Water

题意

题目首先给出一个数组b，数组中的每一个数可以确定平面直角坐标系上的一个点(i,b[i])，两个点可以确定一个容器：两个点分别向x轴引垂线形成的容器，求所有形成的容器中容积（面积）最大的那一个。

题解

首先想到的是暴力法，枚举所有的情况，这样的时间复杂度是O(n^2)，要优化这个算法的话，要么就优化成O(logn)或者O(n)，如果想要优化成O(n)的话就意味着扫描一遍即可。

这样可以找到一个贪心的方法：用两个指针从两边向中间进行扫描，这样我们所求的面积的底在变小，要想扫描到更大的面积的情况只有更长的高才有可能找到，所以就在扫描过程中舍弃掉较小高度的点，让指针继续向中间靠拢。

代码（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size()-1;
        int res = min(height[i], height[j])*(j-i);
        // 从两边向中间扫描
        while(i<j)
        {
            if(height[i] < height[j])
                i++;
            else
                j--;
            res = max(res, min(height[i], height[j])*(j-i));
        }
        return res;
    }
};

更多LeetCode题解，欢迎查看我的GitHub项目