Chương trình C++ tìm diện tích hình chữ nhật lớn nhất trong biểu đồ

Tìm diện tích hình chữ nhật lớn nhất trong biểu đồ (histogram) sử dụng ngăn xếp.

Thuật toán hàm getArea()

Bắt đầu
  Tạo ngăn xếp rỗng.
  Khởi tạo largest_area.
  Với mỗi cột hist[i] (i = 0 đến n-1):
    Nếu ngăn xếp rỗng hoặc hist[i] >= hist[top], push i.
    Ngược lại: pop và tính diện tích với cột nhỏ nhất.
  Pop các cột còn lại và tính diện tích.
Kết thúc

Ví dụ

#include <iostream>
#include <stack>
using namespace std;

int getArea(int hist[], int n) {
    stack<int> st;
    int largest_area = 0;
    int top, 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()) {
        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;
}

Kết quả

Largest area is 16