LeetCode 3

易知，该题的目标是寻找max((i-j)*min(height[i],height[j]))，(0<=j<i<=n)。如果是暴力求解，就用双循环遍历列表，时间复杂度O(n^2)，但这样无疑太低效了。经过观察，发现一些剪枝的办法。目标值的i，j必在最大值M上或其左右两边：即若Ml为左端最大值，Mr为右端最大值，则j<=Ml，i>=Mr。因此可以从两头向中间找，工作量大减。还有每次找下一个i/j，要求要比现在的值大，所以算法设计如下：