Monotonic Stack
LC #85Hard
Maximal Rectangle
Monotonic Stack
AmazonGoogleMetaMicrosoftProblem
Given a binary matrix, find the largest rectangle containing only 1s.
monotonic-stackdynamic-programmingmatrix
Constraints
- ›rows == matrix.length
- ›cols == matrix[i].length
- ›1 ≤ rows, cols ≤ 200
- ›matrix[i][j] is '0' or '1'
Example
Input
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]Output
6Why
The rectangle covering rows 1-2, cols 2-4 has area 6