Leet Code 84 求直方图的最大矩形面积
1.题目
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
有n个非负整数形成的直方图，假设每个矩形区域的边长为1，求出该直方图所包含的面积最大的矩形区域。
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
上面的直方图的每个矩形区域的宽度为1，高度是
[2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
图中的阴影所示的区域即为面积最大的矩形区域，面积大小为10个单位.
Example:
举例:
Input: [2,1,5,6,2,3]
程序输入:[2,1,5,6,2,3]
Output: 10
程序输出: 10
2.题目分析
我们先看一下在每一个矩形位置面积分别是怎么计算的。
位置1:面积2 * 1=2
位置2:面积1 * 6=6
位置3:面积 5 * 2 =10
位置4:面积6*1=6
位置5:面积2*2=4
位置6:面积3*1=3
从上面对面积的计算可以看出，在每个数的位置上，需要向前和向后遍历，遇到比当前位置小的数就停止，所遍历的数的个数，乘以当前位置的数值，就是当前位置的面积。
3.代码展示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#include<iostream>
#include<vector>
//求最左端的索引值
int FindLeftIndex(const std::vector <int> valueVec,const int curIndex)
{
int index = curIndex;
int resultIndex = index;
while(index >= 0)
{
if(valueVec[index] >= valueVec[curIndex])
{
resultIndex = index;
index--;
}
else
{
break;
}
}
return resultIndex;
}
//求最有端的索引值
int FindRightIndex(const std::vector int> valueVec,const int curIndex)
{
int index = curIndex;
int resultIndex = curIndex;
while( index < valueVec.size())
{
if(valueVec[index] >= valueVec[curIndex])
{
resultIndex = index;
index++;
}
else
{
break;
}
}
return resultIndex;
}
//根据所有索引值以及当前位置的值，计算当前位置的矩形面积
int CalcRectArea(const int curValue,const int leftIndex,const int rightIndex)
{
if(rightIndex >= leftIndex)
{
return curValue*(rightIndex-leftIndex+1);
}
return 0;
}
//求面积中最大的
int CalcRectMax(const std::vector int> valueVec)
{
const std::size_t count = valueVec.size();
int sum = 0;
for(std::size_t index = 0 ; index count ; index++)
{
int leftIndex = FindLeftIndex(valueVec,index);
int rightIndex = FindRightIndex(valueVec,index);
int curSum = CalcRectArea(valueVec[index],leftIndex,rightIndex);
if(curSum > sum)
{
sum = curSum;
std::cout << "update Sum [" << leftIndex << "," << rightIndex << "] Sum :" << curSum << std::endl;
}
else
{
std::cout << "Cur Sum [" << leftIndex "," << rightIndex "] Sum :" << curSum << std::endl;
}
}
return sum;
}
int main(int argc,char * argv[])
{
std::vector<int> orgIntVec={2,1,5,6,2,3};
std::cout << CalcRectMax(orgIntVec) << std::endl;
return 0;
}
|
4. 程序输出
update Sum [0,0] Sum :2
update Sum [0,5] Sum :6
update Sum [2,3] Sum :10
Cur Sum [3,3] Sum :6
Cur Sum [2,5] Sum :8
Cur Sum [5,5] Sum :3
10
与上图的分析结果一致。