Stack1 leetcode 85 - Maximal Rectangle https://leetcode.com/problems/maximal-rectangle/ 풀이 모든 시작, 끝에 대해 사각형을 비교해보면 $O(n^4)$만에 찾을 수 있다. 여기서 조금씩 개선해보자. matrix[i][j]가 있을 때 모든 i, j 쌍에 대해서 비교하지 말고, 아래와 같이 높이 배열을 사용하면 개선할 수 있다. height[i][j] = matrix[i][j]부터 위에(같은 열) 존재하는 연속된 1의 개수 이렇게 height[i][j]를 정의하면 모든 $n^2$개의 행의 쌍이 아닌 고정된 행에서만 비교하면 되기 때문에 $O(n^3)$만에 구할 수 있다. i는 $O(n)$으로 줄였지만 여전히 height 하나의 행에서 최대 직사각형을 찾기 위해 $O(n^2)$이 필요하다. 모든 인덱스에 대해.. 2020. 10. 13. 이전 1 다음
