Hình chữ nhật lớn nhất trong ma trận nhị phân C++

Cho ma trận 2D nhị phân chứa 0 và 1. Tìm hình chữ nhật lớn nhất chỉ chứa 1 và trả về diện tích của nó.

Giải thuật

Chuyển bài toán thành tìm hình chữ nhật lớn nhất trong histogram cho mỗi hàng:

• Định nghĩa hàm getAns(vector<int> a) tính diện tích lớn nhất trong histogram:
  • Sử dụng stack lưu chỉ số, duyệt mảng a.
  • Khi a[i] >= đỉnh stack → push i.
  • Ngược lại: pop stack, tính chiều cao = a[top], chiều rộng = i (nếu stack rỗng) hoặc i - stack.top() - 1. Cập nhật diện tích max.
  • Sau vòng lặp, xử lý các phần tử còn lại trong stack.
• Từ main:
  • Khởi tạo mảng height kích thước m (số cột) = 0.
  • Duyệt từng hàng i: với mỗi cột j, nếu x[i][j] == '1' thì height[j]++, ngược lại height[j] = 0.
  • Gọi getAns(height) và cập nhật kết quả max.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int getAns(vector<int> a) {
        stack<int> st;
        int i = 0;
        int ans = 0;
        while(i < a.size()) {
            if(st.empty() || a[i] >= a[st.top()]) {
                st.push(i);
                i++;
            } else {
                int height = a[st.top()];
                st.pop();
                int width = st.empty() ? i : i - st.top() - 1;
                int area = height * width;
                ans = max(ans, area);
            }
        }
        while(!st.empty()) {
            int height = a[st.top()];
            st.pop();
            int width = st.empty() ? a.size() : a.size() - st.top() - 1;
            int area = height * width;
            ans = max(ans, area);
        }
        return ans;
    }

    int maximalRectangle(vector<vector<char>>& x) {
        int ans = 0;
        int n = x.size();
        if(!n) return 0;
        int m = x[0].size();
        vector<int> height(m, 0);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(x[i][j] == '1') height[j]++;
                else height[j] = 0;
            }
            ans = max(ans, getAns(height));
        }
        return ans;
    }
};

int main() {
    vector<vector<char>> v = {
        {'1','0','1','0','0'},
        {'1','0','1','1','1'},
        {'1','1','1','1','1'},
        {'1','0','0','1','0'}
    };
    Solution ob;
    cout << (ob.maximalRectangle(v));
    return 0;
}

Đầu vào

{{'1','0','1','0','0'}, {'1','0','1','1','1'}, {'1','1','1','1','1'}, {'1','0','0','1','0'}}

Đầu ra

6