Explination of the stack solution (python solution)
To get the bigest rectangle area, we should check every rectangle with lowest point at i=1...n.   \n\nDefine Si := the square with lowest point at i. \nTo calcu
To get the bigest rectangle area, we should check every rectangle with lowest point at i=1...n.   \n\nDefine `Si := the square with lowest point at i`. \nTo calculate faster this `Si` , we have to use a stack `stk` which stores some *indices*. \n\nThe elements in stk satisfy these **properties**:   \n\n1. the indices as well as the corresponding heights are in ascending order   \n2. for any adjecent indices i and j (eg. s=[...,i,j,...]), any index k between i and j are of height higher than j: \nheight[k]>height[j]   \n\nWe loop through all indices, when we meet an index `k` with height lower than elements in stk (let's say, lower than index `i` in  `stk`), we know that the right end of square `Si` is just `k-1`. And what is the left end of this square? Well it is just the index to the left of `i` in stk ! \n\nAnother important thing is that we should append a 0 to the end of height, so that all indices in stk will be checked this way. \n\n\n    class Solution(object):\n    def largestRectangleArea(self, height):\n        """\n        :type height: List[int]\n        :rtype: int\n        """\n        mx = 0\n        stk = []\n        height.append(0) # very important!!\n        for k in xrange(len(height)): \n            while(stk and height[k]<height[stk[-1]]):\n                rect = height[stk.pop()] * (k if not stk else k-stk[-1]-1)\n                mx = max(mx, rect)\n            stk.append(k)\n        return mx
['Python']