腾讯2014年实习生招聘试题(最后一题)

给定n块木板A[1...n]，高度记为A[i]，每块目标高度不等，宽度相等，用这些木板排列成一面木板墙，木板排列好后，求解木板墙中最大的矩形面积，请设计算法求得木板墙最大的矩形面积，并分析算法效率。

举例说明，如下图所示的木板排列，最大矩形面积为深灰色区域，即4*3=12。

分析： 扫描数组，计算出每个以A[i]为高的矩形面积，再找出最大值即可。

对于A[i]，分别向前和向后扫描，若高度大于等于A[i]，则以A[i]为高的矩形面积加上A[i].

很显然，算法复杂度为O(n^2).

C语言实现代码如下：

#include <stdio.h>

int get_max(int a[], int n)
{
    int i, j, tmp;
    int result = a[0];
    for (i = 0; i < n; i++) {
        tmp = a[i];
        for (j = i-1; (j >= 0) && (a[j] >= a[i]); j--) {
            tmp += a[i];
        }
        for (j = i+1; (j < n) && (a[j] >= a[i]); j++) {
            tmp += a[i];
        }
        if (tmp > result)
            result = tmp;
    }
    return result;
}

int main(void)
{
    int a[8] = {6, 4, 5, 0, 2, 7, 1, 2};
    printf("%d\n", get_max(a, 8));
    return 0;
}

其他网友提供的O(n^2)算法

private static void getbiggestrectangle(int[] a) {
    int len = a.length;
    int sumsize = a[0];
    int l = 0, r = 0;
    for (int i = 0; i < len; i++) {
        int min = a[i];
        for (int j = i; j < len; j++) {
            if (a[j] < min)
                min = a[j];
            if (min * (j - i + 1) > sumsize) {
                sumsize = min * (j - i + 1);
                l = i;
                r = j;
            }
        }
    }
}