20200404
Plan
leetcode每日一题 11
Notes
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
解法： 1.暴力法 遍历任意两条线之间的面积，取最大值。 时间复杂度：O(n^2) 空间复杂度：O（1）
2.双指针法 用一个头指针和一个尾指针分别指向数组的头部和尾部，然后计算面积取最大值，之后将短的线向长的线靠近1。 理解： 为什么是移动短的线？ 首先面积是受短的线影响，在移动的过程中，边长在不断的变短，如果想要面积变大，那必须找到更高的线，所以保留两条线中较长的一条，将短的线移动，希望找到更高的线。