问题
给定一个非负数的数组,数组中的每个值代表一个柱子的高度,柱子的宽度是1。两个柱 子之间可以围成一个面积,规定:面积=两根柱子的最小值*两根柱之间的距离。
比如数组[3,4,2,5]。3 和 4 之间围成的面积为0,因为两个柱子是相邻的 0,中间没有距离.
3 和 2 之间围成的面积为 2,因为两个柱子的距离为 1,且 2 是最短的柱子,所以面积=1*2。
3 和 5 之间围成的面积为 6,因为两个柱子的距离为 2,且 3 是最短的柱子,所以面积=3*2 = 6;
求在一个数组中,哪两个柱子围成的面积最大,并返回值。 要求:实现时间复杂度 O(N),额外空间复杂度 O(1)的解法
思路
与短板原理类似，在此问题中两柱子围成的面积取决于高度较小的一端。使用双指针又可轻松破解此题
自然想法，从左到右依次遍历，需要两个for语句。时间复杂度为⊖(n^2)
而我们的老朋友双指针，可以将时间复杂度由⊖(n^2)降到⊖(n)，也就是遍历一遍就可得到最大面积.随着两个工作指针的移动，可以枚举出所有两个柱子之间的面积的情况，那么关键问题就是，它们如何按着什么样的规则移动。
Left和Right的移动规则，谁小就向中间方向移动哪个，左右相遇循环结束为什么谁小移动谁，我们通过一个例子，就能直观地认识到此算法的可行性
算法流程示例如下
假设当前数组6 8 ... 7
现在l 指向 6, r 指向 3, l与r之间的距离为10，max变量用来保存当前面积最大值。max = 6 * 10；根据谁小谁移动原则，l向右移动一位，此时l指向8.max的值变为7 * 9 = 63.倘若我们移动r指针，由于l固定指向6，移动后的距离减少，必然导致两柱子之间的面积减少。
核心代码
int maxArea(int *arr)
{
if (arr == NULL || length < 3)
{
return 0;
}
int res = -1;
int l = 0;
int r = length - 1;
while (r - l > 2)
{
if (arr[l] < arr[r])
{
res = max(res, arr[l] * (r - l - 1));
l++;
}
else
{
res = max(res, arr[r] * (r - l - 1));
r--;
}
}
return res;
}