DiffPush Tier Stack and Queues · Monotonic Stack and Queue O(rows * cols) · O(cols)
A datacenter floor maps occupied racks as 1s and free bays as 0s. Facilities planning wants the largest rectangular block of contiguous free bays to reserve for a cooling unit. Scanning row by row, each row's free-bay heights form a skyline whose largest inscribed rectangle is measured with the histogram routine.
Input: A binary matrix given as rows of 0/1 integers.
Output: Return the area of the largest rectangle containing only 1s.
1 <= rows, cols <= 200matrix[i][j] is 0 or 1Input: {"matrix":[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]}
Output: 6
Rows 2-4, columns 3-5 form a 2x3 block of ones with area 6.
Input: {"matrix":[[0]]}
Output: 0
No free bay exists, so no rectangle can be reserved.