前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 11 水池蓄水问题

LeetCode 11 水池蓄水问题

作者头像
TechFlow-承志
发布2020-03-05 20:15:14
1.4K0
发布2020-03-05 20:15:14
举报
文章被收录于专栏:TechFlow

点击上方蓝字,和我一起学技术。

Link

https://leetcode.com/problems/container-with-most-water/

Difficulty

Medium

题意

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

样例

代码语言:javascript
复制
Input: [1,8,6,2,5,4,8,3,7]
Output: 49

题解

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

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

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

代码语言:javascript
复制
for i in range(n):
  for j in range(i+1, n):
    ret = max(ret, (j-i) * min(a[i], a[j]))
return ret

我们来思考怎么优化,显然大部分情况下

的算法往往都不是最优解。考虑一个很简单的问题,为什么取最左边和最右边的隔板不行呢?这样不是矩形的长最长么?

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

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

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

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

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

5 10 X .. X 4 5

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

5 10 X .. X 11 5

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

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

代码语言:javascript
复制
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

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

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-02-01,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Coder梁 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Link
  • Difficulty
  • 题意
  • 样例
  • 题解
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档