在柱状图中找最大的矩形
在柱状图中找最大的矩形：给一组非负的整数来表示一个柱状图，设计一个算法找到最大面积的能适合到柱状图内的矩形。比如，对与这组数，1 2 3 4 1 ，有两种可能的方案，一种是适合到 2 3 4 内的矩形，面积是 2*3；另一种是适合到 3 4 内的矩形，面积是 3*2。你觉得能有O(n)算法吗？
这是一道Google的面试题。下面给出我的解答方法，我的设定是所有柱状图的高度在0-10之间。
1 #include <iostream>
2 #include <vector>
3
4 using namespace std;
5
6 int MaxRectBarChart(vector< int > barChart)
7 {
8 int i_areaArray[ 11 ] = {};
9 int i_tempareaArray[ 11 ] = {};
10 vector< int >::iterator iter = barChart.begin();
11 int max = 0 ;
12 for (; iter != barChart.end(); iter++ )
13 {
14 for ( int i = 1 ; i <= *iter; i++ )
15 {
16 i_tempareaArray[i] += i;
17 }
18 for ( int i = *iter + 1 ; i < 11 ; i++ )
19 {
20 if (i_tempareaArray[i] > i_areaArray[i])
21 i_areaArray[i] = i_tempareaArray[i];
22 i_tempareaArray[i] = 0 ;
23 }
24 }
25 for ( int i = 1 ; i < 11 ; i++ )
26 {
27 if (max < i_areaArray[i])
28 max = i_areaArray[i];
29 }
30 return max;
31 }
32
33 int main()
34 {
35 vector< int > iv_highArray;
36 int i_insert;
37 while (cin >> i_insert)
38 {
39 iv_highArray.push_back(i_insert);
40 }
41 cout << " Max Rectangle area is " << MaxRectBarChart(iv_highArray) << endl;
42 return 0 ;
43 }
还有一道类似的，可以作为上一道题扩展的Google面试题：
在一个位图中找面积最大的白色矩形：给你一个N*N的黑白位图，找一个面积最大的全白色的矩形。注意了，是一个矩形，不是任意一个白色相连的区域。你的算法能达到O(n*n)吗？
标签: 算法 Google 面试题 柱状图 最大面积
作者： Leo_wl
出处： http://HdhCmsTestcnblogs测试数据/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did48010