Python每日一练-----通过简单盛水问题了解省时省力的指针，动态规划
（第六天）昨天搬砖，今天盛水。
题目：
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。（你不能倾斜容器。）
示例
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
n == height.length2 <= n <= 1050 <= height[i] <= 104
题目分析：求最大盛水量就是求最大的矩形面积。矩形的宽就是两竖直边的距离假设第一条是i，第二条是i+j，宽就是i+j-i=j，矩形的高就是min（height[i]，height[i+j]）所盛水的高度取决于最低的那块板。面积s=j*min（height[i]，height[i+j]）。min（）为python内置函数，表示取最小值。
先来正常做法，暴力解题
def maxArea(height): max = 0 # 初始化最大容积 for i in range(len(height)): # 左边的容器边 for j in range(1, len(height)): # 右边的容器边 if i + j = height[i]: # 取两容器边最短的边 s = j * height[i]# 求面积 else: s = j * height[i+j] if s > max: # 如果新的面积大于之前的最大面积，将最大面积的值换做为s max = s return max注意面积s=j*min（height[i]，height[i+j]）而不是s=j*abs（height[i] - height[i+j]），abs()是python内置函数表示取绝对值。第二个if语句可以使用min（）函数替换。
def maxArea(height): max = 0 # 初始化最大容积 for i in range(len(height)): # 左边的容器边 for j in range(1, len(height)): # 右边的容器边 if i + j max: # 如果新的面积大于之前的最大面积，将最大面积的值换做为s max = s return max这种暴力解题简单粗暴，但是只要height的列表长度足够长，所花的时间为O(n^2)，就会运行得很慢。比如这样的长列表
计算速度比较慢。下面介绍速度比较快的指针算法。
我们可以假设height首位各有一条指针x，y。
当指针x对应的高度小于y对应的高度时，指针x向右移动1（x += 1）。
当指针y对应的高度小于x对应的高度时，指针y向左移动1（y -= 1）。
如果指针y对应的高度等于x对应的高度时，随意移动一个指针。
不断重复这一过程直到x与y重合。
以题目为例：
开始x，y位于首尾。x对应高度为1，y对应高度为7，面积s=1*8=8
接着1<7，指针x向右移动1，此时x对应高度为8，面积s=7*7=49
接着8>7，指针y向左移动1，以此类推。
那么问题来了，为什么要这么移动呢，为什么移动较低的指针而不是交高的指针？从感觉上我们可以知道，移动指针会使两指针之间的距离变小，意为着矩形的宽变小。这时移动对应高度最低的指针到下一个位置它对应的高度可能变高，可以弥补宽度变小。但是移动指针到下一位置对应高度也可能变小。
现在我们可以设 x<=y ,两指针间距离为 t，h(y),h(x)表示x，y指针对应的高度。
那么对应的面积为 s=min[h(y), h(x)]*t.
移动y指针：这时我们可以肯定的是y指针无论怎么移动，新面积s1始终会小于s。因为y的移动有两种情况，
1.h(y)变大，那么h(y)仍大于h(x), min[h(y), h(x)],取得的依然是h(x).然而t减小，所以s1<s
2.h(y)变小，h(y)<h(x),这时min[h(y), h(x)]取得h(y),对应高度减小，且t减小，所以s1<s
移动x指针：
设x指针对应新高度为h(x1),新距离为t1，这时 s=min[h(y), h(x)]*t <= s=min[h(y), h(x1)]*t1
1.当h(x1) > h(x)时，min[h(y), h(x)] = min[h(y), h(x1)]
2.当h(x1) = min[h(y), h(x1)]
因为 t1<t
所以必有 s=min[h(y), h(x)]*t < s=min[h(y), h(x1)]*t1
证明完，我们用代码实现
def maxArea(height):x = 0 # 开始时的头指针y = len(height) - 1 # 尾指针s = 0 # 初始化面积while x < y: # 限制条件，当x，y指针重合时停止 area = min(height[x], height[y]) * （y - x) # 取对应高度最小值 s = max(s, area) # 比较新旧面积，取最大面积 if height[x] <= height[y]: # 根据对应高度移动指针 x += 1 else: y -= 1return s # 返回面积这样的算法花费时间为O(n)。比O(n^2)省时多了。
来源参考：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/