Dùng ngăn xếp đơn điệu (monotonic stack).

Duyệt từng cột, duy trì một stack các chỉ số theo chiều cao tăng dần. Khi gặp cột có chiều cao nhỏ hơn đỉnh stack, ta pop và tính diện tích hình chữ nhật với cột vừa pop làm chiều cao.

Với mỗi cột được pop, chiều rộng là \(i - left - 1\) với \(left\) là chỉ số của phần tử dưới đỉnh stack (hoặc \(-1\) nếu stack rỗng).

Độ phức tạp \(O(N)\).

Hướng dẫn giải

Sử dụng thuật toán phù hợp để giải quyết bài toán.

Mã nguồn C++

// Giải thuật st cho bài toán st-max-rect\n#include <bits/stdc++.h>
using namespace std;

int main() {
    // Doc du lieu dau vao
    ios::sync_with_stdio(0); cin.tie(0);
    // TODO: implement solution
    cout << "\n";
    return 0;
}