โปรแกรม 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