Hình chữ nhật tối đa trong C ++

Giả sử chúng ta có một ma trận nhị phân 2D trong đó các giá trị 0 và 1 có mặt. Chúng ta phải tìm hình chữ nhật lớn nhất chỉ chứa 1s và trả về diện tích của nó.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau−

Xác định một hàm được gọi là getAns, điều này sẽ nhận mảng một
tạo ngăn xếp st, i:=0, ans:=0
while i
- nếu ngăn xếp trống hoặc [i]> =trên cùng của ngăn xếp, sau đó chèn i vào st, tăng i lên 1
- mặt khác -
  - height:=a [top of stack], xóa khỏi stack
  - width:=i khi ngăn xếp trống, ngược lại i - top of st - 1
  - diện tích:=chiều cao * chiều rộng
  - ans:=max of ans và area
trong khi st không trống
- height:=a [top of st], xóa khỏi ngăn xếp
- width:=kích thước của a khi st trống, nếu không thì kích thước của a - top of st - 1
- diện tích:=chiều cao * chiều rộng
- ans:=max of ans và area
trả lại ans
Từ phương thức chính, thực hiện như sau -
ans:=0, n:=kích thước của x
nếu n không, thì trả về 0
m:=kích thước của x [0]
tạo một chiều cao mảng có kích thước m
cho tôi trong phạm vi từ 0 đến n - 1
- cho j trong phạm vi 0 đến m - 1
  - nếu x [i, j] =1 thì tăng chiều cao [j] lên 1, nếu không thì tăng chiều cao [j]:=0
- ans:=max of ans và getAns (height)
trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);;
      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;
   }
};
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));
}

Đầu vào

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

Hình chữ nhật tối đa trong C ++

Ví dụ (C ++)

Đầu vào

Đầu ra