初级编程通关练习题 #16 – 面积最大值

给定一组整数数组,数组里的每一个数值都代表长方形的边长,另外一边的边长为数值之间的距离(每个数值和相邻数值之间的距离都为 1)请找出该长方形的最大面积。

输入样例:

[6, 16, 9, 12, 16, 7, 13, 10, 15, 17]

输出样例:

128

在上面的输入样例中,面积最大值为第二个数值16到最后数值17之间的区域,如下图所示。两个数值之间的距离为8,16 x 8 = 128。

max area

算法思路:

  • 需要准备两个指针,一个从头往后移动,另外一个从尾往前移动。
  • 每次移动指针时检查当前指针指向的两个数值所组成的面积,如果比已经找到的最大值要大,则替换最大值。
  • 每次只能移动两个指针其中的一个,当前数值最大的那个指针保持不动,移动另外一个指针。
  • 每次移动指针后,需要再次比较两个数值来决定下次移动哪一个指针。