短板原理之优化策略

来自:光城(微信号:guangcity),作者:lightcity

LeetCode之盛最多水的容器(14)

0.说在前面1.问题2.思路算法3.作者的话

0.说在前面

又到了周二,我们常规操作,leetcode刷题,本次刷题题目为盛最多水的容器

下面我们一起来分析这道题的思路与算法!

1.问题

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

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

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

示例:

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

2.思路算法

思路一:暴力法

直接暴力解决这道题。

这道题其实思路很简单,很简单,暴力法,真的so easy,直接遍历双重循环,O(n^2)时间复杂度,循环中更新最大面积就可以了。

这里运用到了木桶的短板原理

实现

class Solution:
    def maxArea(self, height):
        maxArea = 0
        for i in range(1,len(height)+1):
            for j in range(i,len(height)+1):
                currentArea = (j-i)*min(height[i-1],height[j-1])
                if currentArea>maxArea:
                    maxArea = currentArea
        return maxArea

可惜超时!该方法放弃!

思路二:双指针法

我们知道当宽度最大,高度最大也就是面积最大,直接为最优解,所以这里从两边定义位置,逐渐逼近,直到选择最优的面积!

选择最优面积策略是,当左边比右边高度小,则更新左边,否则更新右边,这样遍历保证了可以使得面积最大被找出来!

实现

时间复杂度O(n),空间复杂度O(1)

class Solution:
    def maxArea(self, height):
        maxArea=0
        low = 0
        high = len(height)-1
        while low<high:
            currentArea = (high - low) * min(height[high], height[low])
            if currentArea > maxArea:
                maxArea = currentArea
            if height[high]>height[low]:
                low+=1
            else:
                high-=1
        return maxArea

提交结果

思路三:思路二优化

这个算法是对上述算法二的优化,优化策略在于移动次数!

这里的移动次数是按照如下方法来进行:

(1)首先跟做左右两端点,计算出初始面积,然后判断左右端点所对应的高度。

(2)左边高情况:则根据左端点是否小于右端点进入循环,因为此时左边高,我们得不断调整右端点,当我们调整右端点时,我们寻找右端点比之前的原始右端点对应的高度大,则说明更新有意义了,然后更新为右端点的当前高度,判定是否高于左端点对应高度,如果高于左端点对应高度,则进入(3)。

(3)右边高情况:还是根据左端点是否小于右端点进入循环,因为此时右边高,我们得不断调整左端点,当我们调整左端点时,我们寻找左端点比之前的原始左端点对应的高度大,则说明更新有意义了,然后更新为左端点的当前高度,判定是否高于右端点对应高度,如果高于右端点对应高度,则进入(2)。

(4)循环判断左端点是否小于右端点,是则重复上述操作,否则退出循环,返回最大面积!

实现

时间复杂度为O(n),空间复杂度为O(1),这里解释一下时间复杂度为何为O(n),我们第一眼看上去有两个循环,想到了O(n^2),但是你有没有仔细观察,内部的循环是影响外层循环,我们按照最坏情况,当左右两端点直接为最优解时,我们相当于不断在更新左边或者右边某一端点的位置,直到最终左右两端点位置一致,循环结束,实质最多对循环的每个元素遍历一次而已!

好好理解一下这里的时间复杂度,确实比上述算法要优一点!

class Solution(object):
    def maxArea(self, height):
        # 最左边
        m1 = height[0]
        # 最右边
        m2 = height[-1]
        left = 0
        right = len(height) - 1
        # 根据左右断点,计算一次面积
        ans = min(height[right], height[left]) * (right - left)
        # 左边比右边小进入循环
        while left < right:
            # m1与m2存储的是高度!比较高度大小
            # 左边高
            if m1 >= m2:
                # 循环条件
                while right > left:
                    # 找到比右边高度大的右边位置
                    if height[right] > m2:
                        # 更新右边大高度m2
                        m2 = height[right]
                        # 更新最大面积
                        ans = max(min(height[right], height[left]) * (right - left), ans)
                        # 判断左右高度
                        if m2 > m1: break
                    right -= 1
            # 右边高
            else:
                while right > left:
                    if height[left] > m1:
                        m1 = height[left]
                        ans = max(min(height[right], height[left]) * (right - left), ans)
                        if m1 >= m2: break
                    left += 1
        return ans

提交结果

参考来源于:
https://leetcode.com/problems/container-with-most-water/discuss?orderBy=recent_activity

3.作者的话

最后,您如果觉得本公众号对您有帮助,欢迎您多多支持,转发,谢谢!

推荐↓↓↓
算法与数据结构
上一篇:一些常用的算法技巧总结 下一篇:拜托,面试别再问我桶排序了!!!