โปรแกรม C++ หาพื้นที่สี่เหลี่ยมผืนผ้าสูงสุดใน Histogram

บทนำ

นี่คือโปรแกรม C++ หาพื้นที่สี่เหลี่ยมผืนผ้าสูงสุดใน Histogram

อัลกอริทึมของฟังก์ชัน getArea()

Begin
  สร้าง stack ว่าง
  เริ่มต้น largest_area
  ลูป while เริ่มจากแท่งแรก สำหรับทุกแท่ง hist[i] โดย i = 0 ถึง n-1:
    ถ้า stack ว่าง หรือ hist[i] สูงกว่าแท่งบนสุดของ stack ให้ push i เข้า stack
    มิฉะนั้น (แท่งนี้ต่ำกว่าบนสุด) ให้ pop บนสุดออกไปเรื่อยๆ จนบนสุดต่ำกว่า คำนวณพื้นที่สี่เหลี่ยมกับแท่งที่ต่ำที่สุด โหนดก่อนบนสุดใน stack คือ left index และ i คือ right index
  Pop แท่งที่เหลือใน stack ถ้าไม่ว่าง และคำนวณพื้นที่กับทุกแท่งที่ pop ออกเป็นแท่งต่ำสุด
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