Chinaunix首页 | 论坛 | 博客
  • 博客访问: 447216
  • 博文数量: 80
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1916
  • 用 户 组: 普通用户
  • 注册时间: 2013-07-11 22:01
个人简介

从事实时计算多年,熟悉jstorm/spark/flink/kafka/rocketMq, 热衷于开源,希望在这里和前辈们一起学习与分享,得到长足的进步!邮箱:hustfxj@gmail.com 我的githup地址是:https://github.com/hustfxj。欢迎和大家一起交流探讨问题。

文章分类

全部博文(80)

文章存档

2017年(11)

2015年(3)

2014年(33)

2013年(33)

分类: C/C++

2014-04-07 11:04:29

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

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

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

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

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

C语言实现代码如下:

点击(此处)折叠或打开

  1. #include <stdio.h>

  2. int get_max(int a[], int n)
  3. {
  4.     int i, j, tmp;
  5.     int result = a[0];
  6.     for (i = 0; i < n; i++) {
  7.         tmp = a[i];
  8.         for (j = i-1; (j >= 0) && (a[j] >= a[i]); j--) {
  9.             tmp += a[i];
  10.         }
  11.         for (j = i+1; (j < n) && (a[j] >= a[i]); j++) {
  12.             tmp += a[i];
  13.         }
  14.         if (tmp > result)
  15.             result = tmp;
  16.     }
  17.     return result;
  18. }

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

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

点击(此处)折叠或打开

  1. private static void getbiggestrectangle(int[] a) {
  2.     int len = a.length;
  3.     int sumsize = a[0];
  4.     int l = 0, r = 0;
  5.     for (int i = 0; i < len; i++) {
  6.         int min = a[i];
  7.         for (int j = i; j < len; j++) {
  8.             if (a[j] < min)
  9.                 min = a[j];
  10.             if (min * (j - i + 1) > sumsize) {
  11.                 sumsize = min * (j - i + 1);
  12.                 l = i;
  13.                 r = j;
  14.             }
  15.         }
  16.     }
  17. }

阅读(1439) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~