欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

11:盛水最多的容器

程序员文章站 2022-07-08 09:40:38
...

问题描述

给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

11:盛水最多的容器
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例

输入:[1,8,6,2,5,4,8,3,7]
输出:49

思路

说实话这题把我绊住了。。

第一次,我想的是暴力法。
双层for循环,对于每一个i,遍历它与每一个j之间的面积,更新最大值。
这样跑出来的算法用leetcode的测试用例跑了2600ms (方法一)

第二次,我改进了一下暴力法:
同样是双层for循环,不过对于值产生了选择,定住一个移动另一个,如果移动的那个移动后还变短了,
证明肯定不行,直接跳过。
这种改进之后的暴力法抛出了620ms 改进了很多,但是还是不行。 (方法二)

第三次,继续改进暴力法:
上面说过,定住一个移动另一个,那可不可以两边都移动呢?两边都移动的话就优化到O(n)了。
对的,可以两边都移动。但是一次只能移动一边。只移动矮的。为啥呢?因为矮的才是决定面积的
关键。为啥这么说?试想一下,如果你这已经是一个矮的了,定住矮的,移动高的,会有3种情况。
1、移动后比原来的高的还矮。(显然面积更小了)
2、移动后和原来高的一样高。(显然面积也变小了,因为虽然高度没变,但是宽度减小了)
3、移动后比原来高的高。(但是没啥用啊,因为算面积要用矮的算,宽度也减小了)
这种方法循环10次才跑了5ms 也就是说一次仅仅是0.5ms(方法三)这也叫双指针法

方法一

Python版

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        maxs = 0
        l = len(height)
        for i in range(l-1):
            for j in range(i+1,l):
                if height[i] > height[j]:
                    low = height[j]
                else:
                    low = height[i]
                t = abs((j-i)*low)
                if maxs < t:
                    maxs = t
        return maxs

方法二

Python版

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        maxs = 0
        l = len(height)
        for i in range(l-1):
            left = height[i]
            current_max = 0
            for j in range(l-1,i,-1):
                if current_max >= height[j]:
                    continue
                current_max = height[j]
                if left > current_max:
                    low = current_max
                else:
                    low = left
                t = abs((j-i)*low)
                if maxs < t:
                    maxs = t
        return maxs

方法三

Python版

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        maxs = 0
        l = len(height)
        start = 0
        end = l-1
        while start != end:
            if height[start] < height[end]:
                low = height[start]
                start += 1
            else:
                low = height[end]
                end -= 1
            t = (end-start+1)*low
            if t > maxs:
                maxs = t
        return maxs

Java版

class Solution {
    public int maxArea(int[] height) {
        int res = 0;
        int left = 0,right = height.length-1;
        while(left < right){
            res = Math.max(res,Math.min(height[left],height[right])*(right-left));
            if(height[left] < height[right]) left++;
            else right--;            
        }
        return res;
    }
}