数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究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
更新于： 30-Jul-2019
291 次查看
广告