Largest Rectangle in Histogram

这道题关键在于看清我们可以以每一个位置的矩形为基准往左右两侧扩张的最大矩形是多少来求得所需要的最大值，看到了这点之后，我们首先要想到的就是如何来知道每一个位置的左右扩张后的最大矩形，进一步思考发现，如果我们维护一个单调上升的栈，并记录当前的位置在栈中就可以做到这一点，例如栈中有元素1，2，3的对应位置时，这时我们遇到一个2，我们就能把3的对应位置弹出并利用当前这个2的位置和3下面的一个元素也就是2这个元素的位置计算出高度不少于3的这个矩形的宽度从而计算出面积了

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        stack = []
        result = 0

        for index, height in enumerate(heights):
            while stack and heights[stack[-1]] > height:
                length = heights[stack.pop()]
                width = index - stack[-1] - 1 if stack else index
                result = max(result, width * length)
            stack.append(index)

        last = len(heights) - 1
        while stack:
            length = heights[stack.pop()]
            width = last - stack[-1] if stack else last + 1
            result = max(result, width * length)

        return result

需要注意最后清空stack时的右边界取值和for循环中不太一样

Maximal Rectangle

这道题可以把它当做上题的follow up来做，如果依然沿用上题的思路，则需要做的就是每次对矩阵中的一行进行1的统计，也就是说在这一行元素为1的情况下看往上数有多少个连续1则相当于有多长高度，这样看的话就相当于把上题的求解过程进行了n次也就是O(nm)了，这样的表现对这道题的要求依然很优秀，也是一个比较巧妙的思路

class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        n = len(matrix)
        if not n:
            return 0

        m = len(matrix[0])
        curList = map(int, matrix[0][:])
        result = 0
        for i in xrange(n):
            if i == 0:
                result = max(self.largestRectangle(curList, m), result)
                continue

            for j in xrange(m):
                curList[j] = int(matrix[i][j]) + curList[j] if matrix[i][j] == '1' else 0

            result = max(self.largestRectangle(curList, m), result)

        return result

    def largestRectangle(self, nums, m):
        stack = []
        result = 0

        for i in xrange(m):
            while stack and nums[stack[-1]] > nums[i]:
                length = nums[stack.pop()]
                width = i - stack[-1] - 1 if stack else i
                result = max(result, length * width)

            stack.append(i)

        while stack:
            length = nums[stack.pop()]
            width = m - stack[-1] - 1 if stack else m
            result = max(result, length * width)

        return result