C ++程序在直方图中查找最大的矩形区域
这是一个C++程序，用于在直方图中查找最大的矩形区域
功能算法getArea()：
Begin
Create an empty stack.
Initialize the largest_area.
Do a while loop start from first bar for every bar hist[i], where i = 0 to
less than n:
If stack is empty or hist[i] is higher than the bar at top of stack, then
push ‘i’ to stack.
Else
this bar is smaller than the top of stack, then keep removing the
top of stack while top of the stack is greater. Calculate area of
rectangle with smallest bar. Element before top in stack is left
index and i is right index for the top.
Pop the remaining bars from stack if stack is not empty and calculate
area with every popped bar as the smallest bar.
End范例程式码
#include<iostream>
#include<stack>
using namespace std;
int getArea(int hist[], int n)
{
stack<int> st;
int largest_area = 0;
int top;
int toparea;
int i = 0;
while (i < n)
{
if (st.empty() || hist[st.top()] <= hist[i])
st.push(i++);
else
{
top = st.top();
st.pop();
toparea = hist[top] * (st.empty() ? i :
i - st.top() - 1);
if (largest_area < toparea)
largest_area = toparea;
}
}
while (st.empty() == false)
{
top = st.top();
st.pop();
toparea = hist[top] * (st.empty() ? i :
i - st.top() - 1);
if (largest_area < toparea)
largest_area = toparea;
}
return largest_area;
}
int main(){
int hist[] = {6,7,4,5,3,2};
int n = sizeof(hist)/sizeof(hist[0]);
cout << "Largest area is " << getArea(hist, n);
return 0;
}输出结果
Largest area is 16
热门推荐
10 姐夫生日条幅祝福语简短
11 新春祝福语大全 英语简短
12 英文节日祝福语简短唯美
13 虎年春节拜年祝福语简短
14 蛋糕班级新年祝福语简短
15 媳妇生日简短祝福语朋友
16 职校离校祝福语大全简短
17 转给爱人红包祝福语简短
18 小班老师六一祝福语简短