在柱状图中找最大的矩形

在柱状图中找最大的矩形：给一组非负的整数来表示一个柱状图，设计一个算法找到最大面积的能适合到柱状图内的矩形。比如，对与这组数，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 面试题 柱状图 最大面积