给定n块木板A[1...n]，高度记为A[i]，每块目标高度不等，宽度相等，用这些木板排列成一面木板墙，木板排列好后，求解木板墙中最大的矩形面积，请设计算法求得木板墙最大的矩形面积，并分析算法效率。
举例说明，如下图所示的木板排列，最大矩形面积为深灰色区域，即4*3=12。
分析：（1）从数组A第一个元素开始，从前向后扫描，记录每一个连续区域中的最低高度，然后计算此连续区域的矩形面积。
（2）从（1）扫描的位置开始，重复（1）。
（3）从所有连续区域的矩形面积中，返回最大的一个矩形面积。
时间复杂度：只需要扫描一遍数组，所以为O（n）.
C++代码如下：
#include <iostream> using namespace std; int get_max(int a[], int n) { int result = 0; int minheight = 0; int temp = 0; int i; int j; for ( i = 0; i < n; i++) { if (a[i]==0) { break; } minheight = a[i]; for (j = i+1; (j <n)&&(a[j]>0); ++j) { if (a[j]<=minheight) { minheight = a[j]; } temp = (j - i + 1)*minheight; } i = j; if (temp>result) { result = temp; } } return result; } int main() { int a[8] = { 6, 4, 5, 0, 2, 7, 1, 2 }; cout<<get_max(a,8)<<endl; return 0; }
很显然，算法复杂度为O(n^2).
腾讯2014年春季笔试题--附件题1,布布扣,bubuko.com
原文：http://www.cnblogs.com/ITxiansheng/p/3675981.html