C++LeetCode 구현(85.최대 사각형)

[LeetCode]85.최대 사각형
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example:
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
이 문 제 는 앞의 그 문제 다.  Largest Rectangle in Histogram  의 확장,이 문제 의 2 차원 행렬 은 각 층 이 위로 하나의 직사 도 를 볼 수 있 습 니 다.행렬 이 몇 줄 이 있 는 지 입력 하면 몇 개의 직사 도 를 형성 하여 모든 직사 도 를 호출 할 수 있 습 니 다.  Largest Rectangle in Histogram  중의 방법 으로 가장 큰 사각형 면적 을 얻 을 수 있다.그러면 이 문 제 는 유일 하 게 해 야 할 것 은 각 층 을 직사 도 의 밑바닥 으로 삼 고 전체 직사 도 를 위로 구성 하 는 것 이다.문 제 는 입력 행렬 의 문 자 를'0'과'1'두 가지 로 제한 하기 때문에 처리 하기 도 상대 적 으로 간단 하 다.방법 은 모든 점 에 대해'0'이면 0 을 부여 하고'1'이면 이전의 height 값 에 1 을 부여 하 는 것 이다.구체 적 인 참조 코드 는 다음 과 같다.
해법 1:

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        int res = 0;
        vector<int> height;
        for (int i = 0; i < matrix.size(); ++i) {
            height.resize(matrix[i].size());
            for (int j = 0; j < matrix[i].size(); ++j) {
                height[j] = matrix[i][j] == '0' ? 0 : (1 + height[j]);
            }
            res = max(res, largestRectangleArea(height));
        }
        return res;
    }
    int largestRectangleArea(vector<int>& height) {
        int res = 0;
        stack<int> s;
        height.push_back(0);
        for (int i = 0; i < height.size(); ++i) {
            if (s.empty() || height[s.top()] <= height[i]) s.push(i);
            else {
                int tmp = s.top(); s.pop();
                res = max(res, height[tmp] * (s.empty() ? i : (i - s.top() - 1)));
                --i;
            }
        }
        return res;
    }
};

우리 도 한 함수 에서 완성 할 수 있 습 니 다.이렇게 코드 는 더욱 간결 해 보 입 니 다.여기 의 height 초기 화 크기 는 n+1 입 니 다.왜 하나 더 있어 야 합 니까?이것 은 우리 가 현재 위치 가 이전 위치 와 같은 높이 보다 작 을 때 만 사각형 의 면적 을 계산 할 수 있 기 때문이다.만약 에 마지막 위치의 높이 가 가장 높다 면 우 리 는 결과 res 를 계산 하고 업데이트 할 수 없 기 때문에 마지막 에 높 은 0 을 추가 해 야 앞의 사각형 면적 을 계산 할 수 있다.이것 은 위의 해법 자 함수 에서 height 말미 에 0 을 추가 하 는 것 과 같은 효과 입 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int res = 0, m = matrix.size(), n = matrix[0].size();
        vector<int> height(n + 1);
        for (int i = 0; i < m; ++i) {
            stack<int> s;
            for (int j = 0; j < n + 1; ++j) {
                if (j < n) {
                    height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0;
                }
                while (!s.empty() && height[s.top()] >= height[j]) {
                    int cur = s.top(); s.pop();
                    res = max(res, height[cur] * (s.empty() ? j : (j - s.top() - 1)));
                }
                s.push(j);
            }
        }
        return res;
    }
};

아래 의 이런 방법의 사고방식 은 매우 교묘 하 다.height 수 조 는 위 와 같다.이곳 의 left 수 조 는 현재 위치 가 1 이 고 그 와 연 결 된 것 이 1 인 왼쪽 경계의 위치(현재 height 가 0 이면 현재 left 는 반드시 0)를 나타 낸다.right 수 조 는 현재 위치 가 1 이 고 그 와 연 결 된 것 이 1 인 오른쪽 경계의 위치 에 1 을 더 하면(1 을 더 하면 길 이 를 계산 하 는 데 편리 함 을 나타 낸다.왼쪽 경계 위 치 를 직접 빼 면 길이 입 니 다).n 으로 초기 화 합 니 다(현재 height 가 0 이면 현재 right 는 n 입 니 다).그러면 임의의 줄 의 j 번 째 위치 에 대해 사각형 은(right[j]-left[j]*height[j]입 니 다.예 를 들 어 주어진 행렬 은 다음 과 같 습 니 다.
[ [1, 1, 0, 0, 1], [0, 1, 0, 0, 1], [0, 0, 1, 1, 1], [0, 0, 1, 1, 1], [0, 0, 0, 0, 1] ]
0 줄:
h: 1 1 0 0 1
l: 0 0 0 0 4
r: 2 2 5 5 5
첫 번 째 줄:
h: 0 2 0 0 2
l: 0 1 0 0 4 
r: 5 2 5 5 5
두 번 째 줄:
h: 0 0 1 1 3
l: 0 0 2 2 4 
r: 5 5 5 5 5
세 번 째 줄:
h: 0 0 2 2 4
l: 0 0 2 2 4 
r: 5 5 5 5 5
네 번 째 줄:
h: 0 0 0 0 5
l: 0 0 0 0 4
r: 5 5 5 5 5
해법 3:

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int res = 0, m = matrix.size(), n = matrix[0].size();
        vector<int> height(n, 0), left(n, 0), right(n, n);
        for (int i = 0; i < m; ++i) {
            int cur_left = 0, cur_right = n;
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    ++height[j];
                    left[j] = max(left[j], cur_left);
                } else {
                    height[j] = 0;
                    left[j] = 0;
                    cur_left = j + 1;
                }
            }
            for (int j = n - 1; j >= 0; --j) {
                if (matrix[i][j] == '1') {
                    right[j] = min(right[j], cur_right);
                } else {
                    right[j] = n;
                    cur_right = j;
                }
                res = max(res, (right[j] - left[j]) * height[j]);
            }
        }
        return res;
    }
};

다시 한 가지 해법 을 살 펴 보 자.여기 서 우 리 는 각 줄 의 연속 1 의 개 수 를 통계 하고 하나의 배열 h 를 사용한다.max,그 중 hmax[i][j]는 i 행,j 번 째 위치 수평 방향 연속 1 의 개 수 를 나타 낸다.만약 matrix[i][j]가 0 이 라면 대응 하 는 hmax[i][j]도 반드시 0 이다.통계 의 과정 은 누적 과 배열 을 구축 하 는 것 과 유사 하 다.유일 하 게 다른 것 은 0 을 만나면 h 를max 설치 0.이 통계 가 나 온 후에 모든 위 치 를 다시 옮 겨 다 니 기만 하면 됩 니 다.먼저 모든 위치의 hmax 값 은 모두 결과 res 를 업데이트 하 는 데 사 용 됩 니 다.높이 가 1 이기 때문에 사각형 으로 볼 수 있 습 니 다.그리고 우 리 는 위로 옮 겨 다 닙 니 다.위(i,j-1)위치 에 도 h 가 있 습 니 다.max 값 이지 만 양자 간 의 작은 값 으로 사각형 을 구성 할 수 있 습 니 다.새로운 사각형 면적 으로 결 과 를 업데이트 합 니 다.이렇게 하면 0 을 만 나 거나 경 계 를 넘 을 때 멈 출 때 까지 계속 위로 옮 겨 다 닐 수 있 습 니 다.그러면 모든 사각형 을 찾 을 수 있 습 니 다.코드 는 다음 과 같 습 니 다.
해법 4:

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int res = 0, m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> h_max(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '0') continue;
                if (j > 0) h_max[i][j] = h_max[i][j - 1] + 1;
                else h_max[i][0] = 1;
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (h_max[i][j] == 0) continue;
                int mn = h_max[i][j];
                res = max(res, mn);
                for (int k = i - 1; k >= 0 && h_max[k][j] != 0; --k) {
                    mn = min(mn, h_max[k][j]);
                    res = max(res, mn * (i - k + 1));
                }
            }
        }
        return res;
    }
};

C++구현 LeetCode(85.최대 사각형)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 최대 사각형 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부탁드립니다!