|
题目：给定n块木板A[1.....n]，高度计为A，每块目标高度不等，宽度相等，用这些木板排列成一面木板墙，木板排列好后，求解木板墙中最大的矩形面积，请设计算法求得木板墙最大的矩形面积，并分析算法效率。
举例说明，如下图所示的木板排列，最大矩形为深色区域，即4*3 = 12.
解题思路：
木桶原理讲，木桶里能装多少水，取决于最短的那块木板。
同样地，最大矩形的面积S， 也取决于组成这个矩形的最短的那块木板高度min，这个矩形包括几块板子，设为length。于是有，
S = min * length .
当最短板的高度min确定时，板子数length越多，S值就越大。
上图中，最短板的高度min可能是A[1.....n]中的任何一个，即可能是0、1、2、4、5、6、7。最终答案中最短板长度必为其中之一。
由于矩形是由连续的几块板子组成的，所以有如下性质：
当确定好min后，length当然是越多S越大。假如取min=1，把min=0的情况排除出去，即在min=0处的左右寻找最大长度，上图可以取到4，最大矩形面积为1*4= 4。假如取min = 2，即有最大矩形面积2*3=6；以此类推。
最后，比较各种min取法得到的最大面积，找出最大值，即为答案。
算法步骤：
1、求数组整体的最小值的位置pos，最大长度为数组长度，求得该情况下，矩形的面积；
2、以pos以界，分别在左右找子数组的最小值，最大长度为子数组的长度，求得两边各一个矩形面积；
3、比较所有矩形的面积，最大值即为答案。
空间复杂度：数组长度+1，首位保存每次分割点的pos位置，面积直接存放到A[pos]处，即实现了原地操作。
时间复杂度：类似快排，为n*logn
其思路实质与快速排序类似，采用递归法，可以实现。
附源代码：Wndows 8.1/visual studio 2013/intel i5-3470 3.20GHZ/4G RAM调试通过
#include <iostream>
#include <ctime>
#include <cmath>
#include <iomanip>
#define N 8
using namespace std;
//求出子数组最小值
int min(int *arr,int first, int last)
{
if (first > last)
{
return -1;
}
int num = arr[first];
int index = first;
for (int i = first+1; i <= last; ++i)
{
if (num > arr[i])
{
num = arr[i];
index = i;
}
}
arr[0] = index;
arr[index] = num*(last - first + 1);
cout << ” From [" << first << "]” << ” to ["<< last << "]“;
cout << “在 [" << arr[0] << “]处取得最小值，” << ” 最大短板面积: =”<< num << “*” << (last - first + 1) << “: ” << arr[index] << endl;
return 0;
}
//随机生成一个数组
int randomSelected(int *arr)
{
for (int i = 1; i < N+1; ++i)
{
arr[i] = rand()/100;
}
return 0;
}
//输出数组
int display(int *arr)
{
for (int i = 1; i < N+1; ++i)
{
cout << arr[i] << setw(4);
}
return 0;
}
//找到数组中的最小值
int findMin(int *arr)
{
int num = -1;
for (int i = 1; i < N + 1; ++i)
{
if (num < arr[i])
{
num = arr[i];
}
}
return num;
}
//递归求出各个矩形面积，原地保存在数组中
int finalMaxSum(int *arr, int start, int end)
{
if (-1 == min(arr, start, end) )
{
return 0;
}
int temp = arr[0];
finalMaxSum(arr, start, temp - 1);
finalMaxSum(arr, temp + 1, end);
return 0;
}
int main()
{
// int a[N + 1] = { 0, 1, 5, 7, 2,0, 3, 9 };
// // randomSelected(a);
// display(a);
// cout << endl;
// finalMaxSum(a, 1, N);
// cout << “最大短板面积” << findMin(a) <<endl;
// int *b = new int[N+1]();
// randomSelected(b);
// display(b);
// cout << endl;
// finalMaxSum(b, 1, N);
// cout << “最大短板面积” << findMin(b) <<endl;
// delete []b;
//
int c[9] = { 0, 6, 4, 5, 0, 2, 7, 1,2 };
display(c);
cout << endl;
finalMaxSum(c, 1, 8);
cout << “最大短板面积” << findMin(c) << endl;
system(“pause”);
return 0;
}
|
