练习题---盛最多水的容器

"""
给定n个非负整数a1,a2,a3...an，每个数代表坐标中的一个点(i,ai)。画n条垂直线，使得垂直线i的两个端点分别为(i,ai)和(i,0)。找出其中的两条线，
使得他们与x轴共同构成的容器可以容纳最多的水.
"""

import random


def func1(nums):
   max_area = 0
   # 两层for循环可以解决该问题
   # 应该减2，前面写成了减1，虽然也是一样的结果，但减2才是正确的
   # 用前面的len(nums)-1个值和后一个值做比较
   for m in range(len(nums) - 2):
      for n in range(m + 1, len(nums)):
         # 水桶嘛，需要的是最小值
         max_area = max(max_area, (n - m) * min(nums[m], nums[n]))
   return max_area


def func2(nums):
   max_area = 0
   left = 0
   # 需要减1，刚写的时候给忽略这事报错了，比较下标要减一才行
   right = len(nums) - 1
   # 采用双指针的方式，分别由列表的两头向中间逼近，值较大的那一个指针不动，移动值较小的指针位置
   while left < right:
      max_area = max(max_area, (right - left) * min(nums[left], nums[right]))
      if nums[left] > nums[right]:
         right -= 1
      else:
         left += 1

   return max_area


nums = [random.randint(1, 30) for _ in range(10)]
print(nums)
print(func1(nums))
print(func2(nums))