Leetcode 84. Largest Rectangle in Histogram

https://leetcode.com/problems/largest-rectangle-in-histogram/

This problem has a special algorithm.

# T:O(n) S:O(n)
class Solution:
    # @param height, a list of integer
    # @return an integer
    def largestRectangleArea(self, height):
        increasing, area, i = [], 0, 0
        while i <= len(height):
            if not increasing or (i < len(height) and height[i] > height[increasing[-1]]):
                increasing.append(i)
                i += 1
            else:
                last = increasing.pop()
                if not increasing:
                    area = max(area, height[last] * i)
                else:
                    area = max(area, height[last] * (i - increasing[-1] - 1 ))
        return area

Run Time: 100 ms