短板原理之优化策略
短板原理之优化策略
LeetCode之盛最多水的容器(14)
0.说在前面1.问题2.思路算法3.作者的话
0.说在前面
又到了周二，我们常规操作，leetcode刷题，本次刷题题目为盛最多水的容器。
下面我们一起来分析这道题的思路与算法！
1.问题
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (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