[DAY29]Largest Rectangle

Largest Rectangle | HackerRank

[Solution1]:List all the rectangles and find the maximum.

[Solution2]: A skyline is broken when a building is lower than previous building. So we use a stack to record the height of each building. When a building’s height is smaller than the top element of the stack. We pop the top element from the stack. And start to form rectangle with the height of the element. And the length of the rectangle would be index minus the top element of the updated stack minus one. Because we may have deleted some of the buildings before the the top element of the updated stack. So we have to minus the top element of the updated stack rather than popped element(the skyline extends to the top element of the updated stack).