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'} }
출력
6