A skyline of buildings of width 1 has heights heights. You want to hang the largest possible rectangular banner flat against the buildings: it must be an axis-aligned rectangle lying entirely within the buildings, touching the ground. Return its maximum area.
Examples
Input: heights = [2, 4, 3, 1, 5, 5]
Output: 10
Explanation: The last two buildings give a 2 x 5 banner. The first three give only 3 x 2 = 6.
Input: heights = [3, 3, 3]
Output: 9
Constraints
0 <= len(heights) <= 10**5,0 <= heights[i] <= 10**4.- Target complexity: O(n) time.
Goals
- Find, for every bar, how far it can stretch left and right
- Maintain a stack of increasing heights and settle bars when they are popped
- Use a sentinel to flush the stack at the end