84. Largest Rectangle in Histogram

Posted on | Edited on | In , |

题目

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

想法

贪心？DP？

DP的话，似乎要N^2的复杂度

先用DP试一下，就是算i~j之间的最小值吧

唔，用DP，简单地算最小值，然后处理，TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        if not heights:
            return 0
        if len(heights) == 1:
            return heights[0]
        dp = [[0 for j in range(len(heights))] for i in range(len(heights))]
        for i in range(len(heights)):
            dp[i][i] = heights[i]
        for l in range(1, len(heights)):
            for i in range(l, len(heights)):
                dp[i - l][i] = min(dp[i - l][i - 1], dp[i][i])
        ans = 0
        for i in range(len(heights)):
            for j in range(len(heights)):
                if dp[i][j] * (j - i + 1) > ans:
                    ans = dp[i][j] * (j - i + 1)
        return ans