資料結構
網路
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 次檢視
廣告