【leetcode】11. 盛最多水的容器

题目内容

11. 盛最多水的容器

思路分析

看到本题目时，表示没有什么头绪，就只好暴力法硬刚，结果超时了...

看了各个题解，几乎全用的双指针法，其中感觉“缩小搜索空间”的这个说法深得我意，特别是那个表格图，感觉讲得非常非常清晰。

首先要明确的是，设下标为i和j，则此时容器的容积为(j - i) * min(height[i], height[j])。

方法：暴力法（超时）

暴力法就是使用每个板子与其他的板子进行两两组合，计算出此组合的最大面积，并更新全局最大面积，最后返回全局最大面积。用双指针参考题解里的图来说，搜索空间如下图白色方格所示：

暴力法搜索空间

时间复杂度为O(n^2)，只能通过54/56个测试用例，但是此方法可以为更高级的双指针法做铺垫。

方法：双指针

参考链接

暴力法做出来之后，很正常的想法是：*有没有一种方法，可以优化暴力法的搜索空间，不计算一些不必要计算的组合呢？*大神们使用双指针法来解决这个问题。

令双指针指向可选板子范围的两侧，注意到此特性：容器的容积由两个板子间的距离和两个板子中低板的高度决定。

设容积V = 低板的高度h * 指针间的距离距离d。若低板确定，指定另一块板：

低板和另一块板间的距离肯定小于d
新比较出的低板的高度肯定小于等于h

因此，低板与其他板的组合的容积肯定小于V。也就是说，可以减小此低板对应的搜索空间，不必再用此低板与其他板组合找“有一块板是此低板时的最大容积”，也就达到了暴力法中我们希望的“ 优化暴力法的搜索空间，不计算一些不必要计算的组合 ”的效果。

我们就可以在确定低板后，计算出此时的V并与最大容积做比较，然后直接将此低板排除出搜索空间，继续对剩余的空间进行搜索，直至双指针相遇。

双指针法缩小搜索空间

代码

#include <vector>

using namespace std;

class Solution {
public:
    // 暴力法 超时 54/56个测试用例
    // 时间复杂度O(n^2)，空间复杂度O(1)
    int maxArea1(vector<int>& height) {
        int n = height.size();
        
        if (n <= 1) return 0;

        int max_area{ 0 }, cur_area{ 0 };

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; j++) {
                cur_area = (i - j) * min(height[i], height[j]);
                max_area = max(cur_area, max_area);
            }
        }

        return max_area;
    }

    // 双指针
    // 时间复杂度O(n)，空间复杂度O(1)
    int maxArea(vector<int>& height) {
        int n = height.size();

        if (n <= 1) return 0;

        int i{ 0 }, j{ n - 1 },  // 初始化双指针
            global_max_area{ 0 }, cur_max_area{ 0 };

        while (i != j) {
            if (height[i] < height[j]) {
                cur_max_area = (j - i) * height[i];
                i++;
            }
            else {
                cur_max_area = (j - i) * height[j];
                j--;
            }

            global_max_area = max(global_max_area, cur_max_area);
        }

        return global_max_area;
    }

    // 双指针 - 写法更好看一点
    // 时间复杂度O(n)，空间复杂度O(1)
    int maxArea(vector<int>& height) {
        int n = height.size();

        if (n <= 1) return 0;

        int l{ 0 }, r{ n - 1 },  // 使用l和r含义更清晰
            //global_max_area{ 0 }, cur_max_area{ 0 };
            max_area{ 0 };  // 仅使用一个变量
        while (l != r) {
            if (height[l] < height[r]) {
                max_area = max(max_area, (r - l) * height[l]);
                l++;
            }
            else {
                max_area = max(max_area, (r - l) * height[r]);
                r--;
            }
        }

        return max_area;
    }
};

int main() {
    Solution s;
    vector<int> input{ 1,2,1 };

    int output;
    output = s.maxArea(input);

    return output;
}

收获

学习了双指针法，学到了这种缩小搜索空间的思想。