11. Container With Most Water
题目:
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.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
题意: 给出一个数组,数组中的每一个数相当于一块板子,两块板子这两个数对应index的距离形成一个桶,痛的容积由最短板的长度(数的大小)以及index的距离的乘积决定,要求求出这个数组最大的容积。
方法一: 暴力解法,计算出所有可能的容积,保留最大的即可,此方法时间复杂度为超时。
代码1:
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
maxcontain = 0
for i in range(n):
for j in range(i, n):
contain = (j - i) * min(height[i], height[j])
if contain > maxcontain:
maxcontain = contain
return maxcontain
方法二: 双指针法,两个指针i, j定位到数组的头部和尾部,若指针i对应的值比指针j要小,那么此时以i为一块木板,容积最大的另一块木板必定为j,因为此时i为短板,容积是由短板和Index距离所决定的,算出此时的容积并将指针i往右移,(指针j左移肯定是不会使得容积增大的,而i右移则有可能使得容积增大)继续进行判断,若指针i对应的值比指针j要大,那么j就是短板,容积由j决定,算出此时的容积,并将指针j左移。直到最后i和j相遇停止,返回最大容积。时间复杂度为。
有人可能会质疑,若在某次的迭代过程中,i对应的值小于j对应的值,此时应该将指针i右移,那么是否存在k,有k>j,且i和k形成的容积是最大容积?这种情况是不可能发生的,因为我们的指针j之所以会由k位置移动到目前的j位置,必然存在位置m, 且m <i, 有m位置对应的值大于k位置对应的值(此时才会左移),那么由m, k形成的容积必然大于i,k形成的容积,因此i,k不会形成最大容积。
代码2:
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
i = 0
j = n -1
maxcontain = 0
while i!= j:
if height[i] >= height[j]:
contain = height[j] * (j - i)
j -= 1
else:
contain = height[i] * (j - i)
i += 1
if contain > maxcontain:
maxcontain = contain
return maxcontain