给定一组整数数组,数组里的每一个数值都代表长方形的边长,另外一边的边长为数值之间的距离(每个数值和相邻数值之间的距离都为 1)请找出该长方形的最大面积。
输入样例:
[6, 16, 9, 12, 16, 7, 13, 10, 15, 17]
输出样例:
128
在上面的输入样例中,面积最大值为第二个数值16到最后数值17之间的区域,如下图所示。两个数值之间的距离为8,16 x 8 = 128。
算法思路:
- 需要准备两个指针,一个从头往后移动,另外一个从尾往前移动。
- 每次移动指针时检查当前指针指向的两个数值所组成的面积,如果比已经找到的最大值要大,则替换最大值。
- 每次只能移动两个指针其中的一个,当前数值最大的那个指针保持不动,移动另外一个指针。
- 每次移动指针后,需要再次比较两个数值来决定下次移动哪一个指针。