当前位置：首页 > article >正文

Leetcode100热题——盛水最多容器

article 2025/1/29 7:53:14

一，题目

描述

11. 盛最多水的容器

二，解答

1，穷举法

直接利用for双循环，计算所有情况的结果。但是时间复杂度是O( $n^{^{2}}$ ).测试结果就是超时。

代码

class Solution {
public:
    int maxArea(vector<int>& height) 
    {
        int max = 0;
        int area;
        int side;
        int len = height.size();

        for(int i = 0;i < len;i++)
        {
            for(int j = i + 1;j < len;j++)
            {
                side = height[i] < height[j] ? height[i] : height[j];
                area = side * (j - i);
                max = max > area ? max : area;
            }
        }

        return max;
    }
};

为什么慢，是因为进行重复计算，去重便是提升关键。

2，优化后的穷举法

我的分析思路：找变量，影响面积就两个变量——高和宽。肯定是越高越好，越接近边界越好。所以想找到最优的那个点。想找到左右两个起始点，在进行for双循环。

代码

class Solution {
public:
    int l, r;
    int lmax,rmax;
    int lIndex,rIndex;
    int max = 0;
    int area,side;

    int maxArea(vector<int>& height) 
    {
        int len = height.size();
        l = len - 1;
        lmax = height[l];
        while(l >= 0)
        {
            if(lmax <= height[l])
            {
                lmax = height[l];
                lIndex = l;
            }
            l--;
        }


        r = lIndex;
        rmax = height[r];
        while(r < len)
        {
            if(rmax <= height[r])
            {
                rmax = height[r];
                rIndex = r;
            }
            r++;
        }
        
        for(int i = rIndex;i < len;i++)
        {
            for(int j = lIndex;j >= 0;j--)
            {
                side = height[j] < height[i] ? height[j] : height[i];
                area = side * (i - j);
                max = max > area ? max : area;
            }
        }

        return max;
    }

};

效果

3,双指针

原理

单一变量原则，定多变一，寻找自变量。避免重复，Don't Repeat Yourself !

不断逼近目标。

面积是由两边距离和最短边决定。每次操作只移动最短那一边，为什么移动短边是关键。

！！！

在双指针法中，尽管水量在某些情况下会减少，但移动较短的边依然是最优策略，原因如下：

1. 水量由较短的边限制

容器的容量取决于两条线之间的距离（宽度）和较短的边（高度）。因此，容器能容纳的水量是由较短的一条线限制的，无论你移动较长的一边还是较短的一边，都只能通过改变较短的一边的高度来可能增加水量。

2. 为什么移动较短的边？

如果我们移动较长的一边： 它的高度对容器水量没有任何影响，因为水量始终是由较短的那一边决定的。移动较长的一边只会减小容器的宽度（即减少水量），因此没有意义。
如果我们移动较短的一边： 我们在尝试寻找更高的线段，这样可能会增加容器的容量。虽然有可能水量会减少，但它也可能变大。如果当前的较短边很小，移动它可能会遇到一个比它更高的边，从而增加水量。

3. 举例说明

假设有数组 height = [1, 8, 6, 2, 5, 4, 8, 3, 7]，指针分别位于 i = 1 和 j = 8（即 height[1] = 8 和 height[8] = 7）。初始水量是：

min(8, 7) * (8 - 1) = 7 * 7 = 49

如果我们移动较长的一边（即 height[1]），变为 i = 2，则：

min(6, 7) * (7 - 2) = 6 * 5 = 30

水量减少了。

但如果我们移动较短的一边（即 height[8]），变为 j = 7，则：

min(8, 3) * (6 - 1) = 3 * 6 = 18

水量仍然减少。但通过这种方式，我们希望最终找到一个更高的线段，带来更大的水量。

4. 通过不断移动较短的一边寻找更大的水量

虽然移动较短的一边的水量有时会减少，但它有可能帮助你找到一个比当前线段更高的线段，从而增加水量。这个策略是基于对“寻找最大水量”这一目标的逐步逼近，每次移动较短的一边，尽可能找到一个能容纳更多水量的新容器。

5. 证明双指针法最优性

假设你现在有一对指针，指向两条线。你可以选择移动较短的一边或较长的一边，但移动较长的一边不会帮助你找到更大的水量。因为水量是由两条线的较短的那一条决定的，所以你需要试图找到一个更高的线段来替代当前的较短的一边。

总结

水量是由较短的边决定的，所以只需要尝试提高较短的一边。
移动较长的边并不会带来任何好处，因为它的高度不会影响水量的增加。
通过移动较短的边，我们有机会找到一个更高的线段，进而可能获得更大的水量。

因此，总是移动较短的边，是因为它可能引导我们找到更大的水量，确保了算法的高效性和正确性。

代码

class Solution {
public:
    int maxArea(vector<int>& height) 
    {
        int len = height.size();
        int l = 0;
        int r = len - 1;
        int max = getArea(height,l,r);
        int area;

        while(l < r)
        {
            if(height[l] > height[r])
            {
                area = getArea(height,l++,r);
                max = max > area ? max : area;
            }
            else
            {
                area = getArea(height,l,r--);
                max = max > area ? max : area;
            }
        }

        return max;
    }


    int getArea(vector<int>& height,int l,int r)
    {
        int side = height[l] < height[r] ? height[l] : height[r];
        return side * (r - l) ;
    }
};

在内存上还能优化。

查看全文

http://www.kler.cn/a/520676.html