短板原理之优化策略

• 2019 年 10 月 5 日
• 筆記

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