算法-数组-盛最多水的容器

用户3578099

发布于 2022-06-10 15:45:39

3570

发布于 2022-06-10 15:45:39

文章被收录于专栏：AI科技时讯AI科技时讯

11.盛最多水的容器

来源：力扣（LeetCode）

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

给定一个长度为 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

解法

暴力法：枚举，从左边界从最左边开始，右边界从左边+1开始，统计最大面积，两层循环；
双指针法：如果左右选在最左边和最右边，宽度最高了，然后往中间收敛，如果高度不如现在的话，那就不用看了，只需要比较高度更高的那根柱子，然后算面积，如果i，j相遇，结束遍历。左右边界同时向中间收敛，左右夹逼

代码实现

方法1 暴力法

python实现

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 暴力法
        n = len(height)
        max_area = 0
        for i in range(n-1):
            for j in range(i+1, n):
                area = min(height[i], height[j]) * (j-i)
                max_area = max(max_area, area)
        return max_area

c++实现

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

复杂度分析

时间复杂度：O(n^2)
空间复杂度：O(1)

方法2 双指针法

python实现

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 双指针法：
        # 如果左右选在最左边和最右边，宽度最高了，然后往中间收敛
        # 如果高度不如我，那就不用看了，只需要比较高度更高的那个棒子，然后算面积，如果i，j相遇，结束遍历。时间复杂度是O(n)
        n = len(height)
        i = 0
        j = n-1
        max_area = 0
        while i < j:
            current_width = j - i
            if height[i] < height[j]:  # 左边小于右边，左边需要右移动
                area = current_width * height[i]
                i += 1
            else:  # 左边大于等于右边，右边需要左移动
                area = current_width * height[j]
                j -= 1
            max_area = max(area, max_area)
        return max_area

c++实现

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

复杂度分析