大致题意
就是求一个数组里所有两个值中较小值和它们之间距离的乘积最大值
解题思路
这题最暴力的方法是遍历，时间复杂度O(n^2)，这样一点都不优雅
当然也有O(n)的，解法如下：
示例数组[1,8,6,2,5,4,8,3,7]
- 选数组的起始和终点，即选1和7间隔为8，此时乘积为1*8
- 最大间隔是8那么，从最大间隔找递减找下去
- 当间隔为7的时候，数组只能被分为[1,8,6,2,5,4,8,3]和[8,6,2,5,4,8,3,7]
- 那么只有可能在被拆分的第二个的数组中，因为没有数组1中有被拆分前边界中的那个更小值而且间隔变短那么它得到的乘积一定会被拆分前小，所以只有可能在被拆分的第二个数组，即边界较大的那个数组
- 根据4得到的结论，一步步缩小间隔，最终得到最大值
int maxArea(vector& height) {
int len = height.size() - 1;
int ans = 0;
int _start = 0, _end = len;
while (_start < _end){
ans = max(min(height[_start], height[_end])*len, ans);
if (height[_start] < height[_end])
_start++;
else
_end--;
len--;
}
return ans;
}
</code></pre>
[完整解答](https://github.com/liuyueweiyu/Leetcode/blob/master/1-50/11.cpp)
