7.20 左程云牛客第3题 （个人学习笔记）

题目：

给定一个非负数的数组，数组中的每个值代表一个柱子的高度，柱子的宽度是 1。两个柱子之间可以围成一个面积，规定：面积＝两根柱子的最小值＊两根柱子之间的距离。比如数组[3,4,2,5]。3 和 4 之间围成的面积为 0，因为两个柱子是相邻的，中间没有距离。3 和2 之间围成的面积为 2，因为两个柱子的距离为 1，且 2 是最短的柱子，所以面积＝1*2。3 和 5 之间围成的面积为 6，因为两个柱子的距离为 2，且 3 是最短的柱子，所以面积＝3*2。求在一个数组中，哪两个柱子围成的面积最大，并返回值。

 要求：实现时间复杂度 O(N)，额外空间复杂度 O(1)的解法

 

解法一：

常规解法：每个位置遍历一遍用一个变量存储最大值

过程例如：

 数组中位置 a[0]   a[1]   a[2]   a[3] 

 数组中值      3        4       2      5

（1）a[0]    与a[2]（不与a[1]比较，应为距离为0，面积为0） 

        3 和2 之间围成的面积为 2，因为两个柱子的距离为 1，且 2 是最短的柱子，所以面积＝1*2

       maxArea=2;

（2）a[0]与a[3]

  3 和 5 之间围成的面积为 6，因为两个柱子的距离为 2，且 3 是最短的柱子，所以面积＝3*2

maxArea=6;

（3）a[1]与a[3]

  4和 5 之间围成的面积为 4，因为两个柱子的距离为 1，且 4 是最短的柱子，所以面积＝1*4

maxArea=6;

最后得 面积最大值为6。

C++代码如下

int maxArea1(int* arr,int length) 
{
	 if (arr ==NULL || length < 3) 
		 return 0;
	 int res =0;
	 for (int i = 0; i < length - 2; i++)
	 {
		 for (int j = i + 2; j < length; j++) 
		 {
			 int min = arr[i]>arr[j] ? arr[j] : arr[i];
			 int cur = (j - i - 1)*min;
			 res = res>cur?res:cur;
		 }
	 }
	 return res;
 }

解法二：

用两个指针  Begin与End分别指向数组头尾，比较2者值，取小者与距离乘积得面积；

由于值小的为面积的瓶颈，故移动值小的,直到2个指针重合。

过程：

（1）  a[0]   a[1]  a[2]  a[3]    a[4]

            3        8       2      5       7

            |                                   |

                Begin                                                  End

    面积为    3*3=9   maxArea=9    

   a[0]<a[4]   Begin++;

(2)

           a[0]   a[1]  a[2]  a[3]  a[4]

            3        8       2      5    7

                      |                      |

                                  Begin                           End

面积为    7*2=14    maxArea=14     

   a[1]>a[4]   End--;

(3)

           a[0]   a[1]  a[2]  a[3]  a[4]

            3        8       2      5    7

                      |                |

                  Begin          End

面积为    5*1=5    maxArea=14    

   a[1]>a[3]   End--;

   结束

C++代码：

 int maxArea2(int*arr,int length) 
 {
	if (arr == NULL ||length < 3) {
		return 0;
	}
	int l = 0;
	int r = length - 1;
	int res =0,cur=0;
	while (l < r-1) 
	{
		if (arr[l] < arr[r]) 
		{
			cur = (r - l - 1)*arr[l++];
			res = res>cur ? res : cur;
		}
		else 
		{
			cur = (r - l - 1)*arr[r++];
			res = res>cur ? res : cur;
		}
	}
	return res;
}