11. 盛最多水的容器

题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

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

提示：

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

地址

https://leetcode.cn/problems/container-with-most-water

题意

二分查找、双指针

思路

这个题目出的很好，典型的双指针解法就不说了，参考官方题解, 主要谈谈二分查找的解法。
二分查找：

我们只需要枚举每个可能的容器的高度即可，即枚举第 $i$ 个容器的高度为 $\textit{height}[i]$。此时 $\textit{height}[i]$ 为容器的右边缘，则此时我们只需要找到容器的最小的左边缘即可，此时我们只需要找到 $j \in [0,i-1]$ 之间最小且满足 $\textit{heigth}[j] \ge \textit{height}[i]$, 找到最小的 $j$ 即可；此时 $\textit{height}[i]$ 为容器的左边缘，则此时我们只需要找到容器的最大的右边缘即可，此时我们只需要找到 $j \in [i + 1, n]$ 之间最大且满足 $\textit{heigth}[j] \ge \textit{height}[i]$, 找到最大的 $j$ 即可，有以下两种二分查找即可：
- 设立新的数组 $left[i]$ 表示 $[0,i]$ 之间的最大值，此时我们知道 $left$ 数组一定是递增的，此时我们即可利用二分查找，找到最小 $j$ 即可，此时容器的容积为 $(i - j) \times \textit{height}[i]$；设立新的数组 $right[i]$ 表示 $[0,i]$ 之间的最大值，此时我们知道 $right$ 数组一定是递增的，此时我们即可利用二分查找，找到最大 $j$ 即可，此时容器的容积为 $(j - i) \times \textit{height}[i]$，我们直接利用二分查找完成上述即可。
- 线段树上二分，这个方法是参考2286. 以组为单位订音乐会的门票中的线段树二分法来解决该问题的，非常好的思考方法。

复杂度分析：

时间复杂度：$O(n \log n)$, 其中 $n$ 为数组的长度。
空间复杂度：$O(n)$, 其中 $n$ 为数组的长度。

代码

二分查找:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int ans = 0;
        vector<int> leftMax;
        vector<int> rightMax;
        /* left to right*/
        for (int i = 0; i < n; i++) {
            auto it = lower_bound(leftMax.begin(), leftMax.end(), height[i]);
            if (it != leftMax.end()) {
                int start = it - leftMax.begin();
                ans = max(ans, (i - start) * height[i]);
            }
            if (i == 0) {
                leftMax.emplace_back(height[i]);
            } else {
                leftMax.emplace_back(max(leftMax.back(), height[i]));
            }
        }
        /* right to left */
        for (int i = n - 1; i >= 0; i--) {
            auto it = lower_bound(rightMax.begin(), rightMax.end(), height[i]);
            if (it != rightMax.end()) {
                int start = it - rightMax.begin();
                ans = max(ans, (n - i - 1 - start) * height[i]);
            }
            if (i == n - 1) {
                rightMax.emplace_back(height[i]);
            } else {
                rightMax.emplace_back(max(rightMax.back(), height[i]));
            }
        }
        return ans;
    }
};

线段树+ 二分：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int n = height.size();
        this->tmax = vector<int>(n * 4 + 1);
        this->height = height;
        buildTree(0, n - 1, 1);
        for (int i = 0; i < n; i++) {
            int x = queryLeft(i, height[i], 0, n - 1, 1);
            int y = queryRight(i, height[i], 0, n - 1, 1);
            res = max(res, height[i] * (i - x));
            res = max(res, height[i] * (y - i));
        }
        return res;
    }

    void buildTree(int l, int r, int idx) {
        if (l == r) {
            tmax[idx] = height[l];
        } else {
            int mid = (l + r) >> 1;
            buildTree(l, mid, idx * 2);
            buildTree(mid + 1, r, idx * 2 + 1);
            tmax[idx] = max(tmax[idx * 2], tmax[idx * 2 + 1]);
        }
    }

    int queryLeft(int end, int val, int l, int r, int idx) {
        if (l > end) {
            return -1;
        }
        if (tmax[idx] < val) {
            return -1;
        }
        if (l == r) {
            return l;
        } else {
            int mid = (l + r) >> 1;
            if (tmax[idx * 2] >= val) {
                return queryLeft(end, val, l, mid, idx * 2);
            }
            if (mid < end) {
                return queryLeft(end, val, mid + 1, r, idx * 2 + 1);
            }
            return -1;
        }
    }

    int queryRight(int start, int val, int l, int r, int idx) {
        if (r < start) {
            return -1;
        }
        if (tmax[idx] < val) {
            return -1;
        }
        if (l == r) {
            return l;
        } else {
            int mid = (l + r) >> 1;
            if (tmax[idx * 2 + 1] >= val) {
                return queryRight(start, val, mid + 1, r, idx * 2 + 1);
            }
            if (start <= mid) {
                return queryRight(start, val, l, mid, idx * 2);
            }
            return -1;
        }
    } 

private:
    vector<int> tmax;
    vector<int> height;
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 算法

← leetcode contest 295 leetcode biweekly contest 79 →

扫描二维码，分享此文章