C++의 최대 직사각형

<시간/>

0과 1 값이 있는 2D 이진 행렬이 있다고 가정합니다. 1만 포함하는 가장 큰 직사각형을 찾아 면적을 반환해야 합니다.

이 문제를 해결하기 위해 다음 단계를 따르겠습니다-

getAns라는 함수를 정의합니다. 이것은 배열 a
를 취합니다.
스택 생성, i :=0, ans :=0
동안 나는 <크기, then
- 스택이 비어 있거나 a[i]>=스택의 맨 위이면 i를 st에 삽입하고 i를 1만큼 증가
- 그렇지 않으면 -
  - height :=a[스택 상단], 스택에서 삭제
  - width :=스택이 비어 있을 때 i, 그렇지 않으면 i – st의 맨 위 – 1
  - 면적 :=높이 * 너비
  - ans :=ans 및 영역의 최대값
st가 비어 있지 않은 동안
- height :=a[st의 상단], 스택에서 삭제
- width :=st가 비어 있을 때 a의 크기, 그렇지 않으면 a의 크기 – top of st – 1
- 면적 :=높이 * 너비
- ans :=ans 및 영역의 최대값
반환
주요 방법에서 다음을 수행하십시오 -
ans :=0, n :=x의 크기
n이 0이면 0을 반환합니다.
m :=x[0]의 크기
m 크기의 배열 높이를 하나 생성
0 ~ n – 1 범위의 i에 대해
- 0 ~ m – 1 범위의 j에 대해
  - x[i, j] =1이면 height[j]가 1 증가하고 그렇지 않으면 height[j] :=0
- ans :=ans 및 getAns(높이)의 최대값
반환

예시(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);;
      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));
}

입력

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

C++의 최대 직사각형

예시(C++)

입력

출력