代码随想录算法训练营第六十天| LeetCode84.柱状图中最大的矩形

84.柱状图中最大的矩形

题目描述: 84.柱状图中最大的矩形.

解法

单调栈

class Solution(object):
    def largestRectangleArea(self, heights):
        heights.append(0)
        heights.insert(0,0)

        res = 0
        st = [0]
        for i in range(1,len(heights)):
            while st and heights[i] < heights[st[-1]]:
                mid = st.pop()
                mid_height = heights[mid]
                if st:
                    left = st[-1]
                    w = i - left -1
                    res = max(res,mid_height*w)
            st.append(i)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

注意两边要加0，这是个反向的接雨水