85370f4532dd1c5ba8fa87a6643ea3e4
Problem 11: Container With Most Water

Problem 11: Container With Most Water

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

难度等级:Medium(中等)

题干

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

题意

给定一连串数组,表示不同高度的墙壁。墙壁之间的间隔为1,我们想要选出两个墙壁。是的这两个墙壁构成的蓄水池的横截面积最大。

样例

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

分析

那道题看明白题意,暴力求解的思路应该已经很清晰了。

这道题的本质上是选择两个尽可能大并且尽可能距离远的数,他们中较小的数和距离的乘积就等于最后的答案。

所以我们只需要枚举所有的起点和终点,就可以找到答案。复杂度是$O(n^2)$。

伪代码:

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

但到这里,我们有一个问题,那就是我们真的有必要枚举所有的情况吗?因为两重循环的复杂度的确是有点大了,有没有什么办法可以不用枚举的呢?

仔细想想其实是有的,不过比较隐蔽。

在阐述思路之前,我们先做两个假设:

top Created with Sketch.