99클럽 3기 코테 스터디 22일차 TIL /[LeetCode] Maximal Rectangle 자바

 

 

 

 

 

 

1. 오늘의 학습 문제 

---

문제

---

 

 

 

https://leetcode.com/problems/maximal-rectangle/

 

 

85. Maximal Rectangle

Hard

10598185Add to ListShare

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = [["0"]]
Output: 0

Example 3:

Input: matrix = [["1"]]
Output: 1

 

Constraints:

• rows == matrix.length
• cols == matrix[i].length
• 1 <= row, cols <= 200
• matrix[i][j] is '0' or '1'.

 

 

 

 

코드

---

 

시도했던 풀이(오답)

import java.util.*;

class Solution {
    static int answer;
    static int size_garo;
    static int size_sero;
    //하, 우, 상, 좌
    static int[] x = {1, 0, -1, 0};
    static int[] y = {0, 1, 0, -1};
    static char[][] M;


    static int[][] memo;
    public int maximalRectangle(char[][] matrix) {
        answer=0;
        M=matrix;
        size_garo = matrix[0].length; //예제- 5
        size_sero = matrix.length; // 예제- 4
        memo = new int[size_sero][size_garo];//방문 여부와 해당 칸을 포함하는 largest rectangle 크기 저장

        for(int i=0;i<size_sero;i++){
            for (int k = 0; k < size_garo; k++) {
                search(i, k);

            }
        }

        return answer;
    }

    private void search(int i, int j) {

        int temp=0;
        Stack<Integer> stack = new Stack<>();

        for (int k = 0; k < 4; i++) { // 상하좌우 네모 그려지는지 탐색
            int a=k;
            int cnt=0;
            while(cnt<4){

                int X = i + x[a];
                int Y = j + y[a];

                //범위 밖이거나, 0이면 아웃
                if (X == size_sero || Y == size_garo || X == -1 || Y == -1 ) {
                    break;
                }
                else {
                    if(M[X][Y]!='0'){
                        stack.add(X);
                        stack.add(Y);
                    }
                    else{
                        break;
                    }
                }
                a= (a==3)? 0  : a++;
                cnt++;

            }
        }

        temp=stack.size()/2;

        if (answer < temp) {
            answer=temp;
        }
        while (!stack.isEmpty()) {

            int b=stack.pop();
            int a = stack.pop();
            memo[a][b]= temp;

        }




    }
}

 

 

 

정답

import java.util.*;

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] heights = new int[cols];
        int maxArea = 0;

        for (int i = 0; i < rows; i++) {
            // 현재 행에 따라 히스토그램 높이를 업데이트
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    heights[j]++;
                } else {
                    heights[j] = 0;
                }
            }
            // 이 행의 히스토그램에서 최대 직사각형 면적 계산
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }

        return maxArea;
    }

    private int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int n = heights.length;

        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }

        return maxArea;
    }
}

 

 

 

 

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL