LeetCode 11 水池蓄水问题

2019/04/10 10:10
阅读数 23

今天给大家分享的是一道LeetCode中等难度的题,难度不大,但是解法蛮有意思。我们一起来看题目:

<br>

Link

Container With Most Water

Difficulty

<font color=orange>Medium</font>

<br>

题意

<br>

给定n个非负整数,表示水库当中隔板的高度每两块隔板之间的距离为1,当下要从n个隔板当中选出两个,在其中注水,并且要使得容纳的水尽量多。请问最多能容纳多少水?可以忽略隔板的宽度,将水库看成是正规的长方体。

<br>

样例:

<br>

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

<br>

题解:

<br>

由于水库可以看成是正规的长方体,所以水库的体积可以简化为横截面积。也就是说我们要选择两个隔板,使得隔板之间围成的矩形面积最大。

<br>

首先思考暴力求解,我们只需要枚举矩形的两边,两边有了之后,矩形的长,也就是两边之间的距离,矩形的宽就是两边的较小值,所以复杂度是$O(n^2)$。

<br>

这样写的代码也很简单,只有几行:

<br>

for i in range(n):
  for j in range(i+1, n):
    ret = max(ret, (j-i) * min(a[i], a[j]))
return ret

<br>

我们来思考怎么优化,显然大部分情况下$O(n^2)$的算法往往都不是最优解。考虑一个很简单的问题,为什么取最左边和最右边的隔板不行呢?这样不是矩形的长最长么?

<br>

不行的原因很简单,因为矩形的长最长的时候,但是矩形的宽不一定很宽。有可能这样的宽很短,就像上面图中展示的一样。如果这时候的结果不是最佳值,那么最佳答案的长一定小于n。如果我们用i和j指代最优解的左右两边的下标,那么显然有1 <= i < j <= n。

<br>

也就是说i, j 的位置应该在1, n的内部。我们可以想象一开始的时候i指向1,j指向n,然后逐渐移动到了最优解的位置。我们应该移动i和j,但是每次应该怎么移动呢?究竟是移动i还是移动j呢?

<br>

其实稍微想一下就能想到答案,应该移动i和j两个当中隔板比较短的那个。假设i的隔板长度小于j,即使移动i,即使碰到了更长的隔板,面积也不会变大,因为j的长度并没有变,它依旧是短板。所以我们只有移动其中较短的那个,才有让矩形面积变大的可能。

<br>

如果i和j的长度一样怎么办?答案是随便移动哪个都一样,有些同学可能还有顾虑。我们不妨使用一下我们之前介绍贪心算法的时候提到的均等假设法。有忘记的同学可以点击下方的链接回顾一下:

<br>

贪心算法与均等假设法

<br>

我们来举个例子,假设水库隔板的情况是:

<br>

5 10 X .. X 4 5

<br>

我们一开始的时候i指向左边的5,j指向右边的5,这时候i和j相等。如果移动左边的i,到10,面积并没有变大。接下来会一直移动右边的j,直到j遇到大于10的为止。并不会出现影响正确结果的情况。如果移动右边的j呢?其实也是一样的,因为如果j没有遇到大于5的元素,无论左边指向什么地方,面积都不会增大。当j遇到5以上的数的时候,必然会移动左边的i,一样可能增大面积。

<br>

5 10 X .. X 11 5

<br>

我们再看这个例子,如果10和11围成的结果是正确答案,那么不论先移动i还是先移动j都是一样的。本质上来说,如果矩形面积要增大,必须要i和j同时指向比当前更大的元素才行,所以先移动哪个并不会影响结果。

<br>

这样一来,写代码就方便了,我们可以人为规定如果出现相等,就移动i。写出来代码如下:

<br>

i, j = 0, n-1
ret = 0
while i < j:
  ret = max(ret, (j - i) * min(a[i], a[j]))
  if a[i] <= a[j]:
    i += 1
  else:
    j -= 1
return ret

<br>

这道题既可以认为是贪心算法,也可以认为是两指针维护区间的问题。不论怎么样解释,写出来的代码是一样的,我个人觉得还是很巧妙的,很适合初学者练手,并且难度也不是很大。希望大家都能领会。

<br>

今天的文章就到这里,如果觉得有所收获,请顺手点个关注吧,你们的支持是我最大的动力。

原文出处:https://www.cnblogs.com/techflow/p/12251595.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部