LeetCode No.84 | StriveZs的博客

LeetCode No.84

LeetCode第八十四题—柱状图中的最大的矩形

自己代码的开源仓库:click here 欢迎Star和Fork :)

题目描述

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

figure.1

以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。

figure.2

1
2
3
4
示例:

输入: [2,1,5,6,2,3]
输出: 10

分析

1
2
3
4
5
6
7
8
例子分析:要保证栈为单调增栈
对于[2,1,5,6,2,3,0] 输入
stack:2 因为1 < 2 因此计算2 得到面积为2 2出栈 1入栈
stack:1 因为5>1 所以5入栈
stack:1 5 因为6>5 所以6入栈
stack:1 5 6 因为 2<6 因此计算6(栈顶) 得到面积6 6出栈 又因为 2<5 因此接着计算5(当前栈顶) 得到面积10 5出栈 2入栈
stack:1 2 因为2>3 所以3入栈
stack:1 2 3 访问结束,依次计算3 2 1 这里可以在高度柱表中引入一个0

计算图表:

figure.0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution(object):
def TimeOut(self, heights):
"""
:type heights: List[int]
:rtype: int

感觉有点类似水桶漏水那道题
核心思想:
暴力法,依次遍历每个柱子,然后依次找它两边比它短的柱子,并累加面积即可
注意特别处理最两边的柱子
如果当前柱子的大小比前一个柱子大,则在上一个柱子面积上累加,只需要往后找比当前柱子长度大于等于的相邻柱子即可
"""
maxInt = 0
for i in range(len(heights)):
if heights[i] == 0:
continue
num = 0 # 计数菌 大于等于当前柱子值的柱子数目,如果存在比当前柱子数目小的柱子 则结束统计
for j in range(i+1,len(heights)):
if heights[j] > heights[i]:
num += 1
else:
break
if i == 0:
maxInt = max(maxInt,(num+1) * heights[i])
elif heights[i - 1] < heights[i]:
maxInt = max(maxInt,num * heights[i] + heights[i])
else:
pre = i
for j in range(0,i+1):
if heights[i-j] < heights[i]:
break
pre = i-j
maxInt = max(maxInt,(i-pre)*heights[i] + num*heights[i] + heights[i])
return maxInt
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int

上一个暴力解法成功超时了,下面是参考带佬写的单调栈来求解,看评论JAVA版本的暴力解法是可以通过,Python党震怒
思路:
对于一个高度,如果能得到向左和向右的边界
那么就能对每个高度求一次面积
遍历所有高度,即可得出最大面积
使用单调栈,在出栈操作时得到前后边界并计算面积
单调栈介绍:
1.单调栈分为单调递增栈和单调递减栈
11. 单调递增栈即栈内元素保持单调递增的栈
12. 同理单调递减栈即栈内元素保持单调递减的栈

2.操作规则(下面都以单调递增栈为例)
21. 如果新的元素比栈顶元素大,就入栈
22. 如果新的元素较小,那就一直把栈内元素弹出来,直到栈顶比新元素小

3.加入这样一个规则之后,会有什么效果
31. 栈内的元素是递增的
32. 当元素出栈时,说明这个新元素是出栈元素向后找第一个比其小的元素
"""
maxInt = 0 # 最大值
stack = [] # 单调增栈
heights.insert(0,0) # 首尾+一个0 防止下面right left超出边界
heights.append(0)
# 计算方式不是顺序计算,是先从最大的柱开始计算,依次计算小的柱
for i in range(len(heights)):
while len(stack) != 0 and heights[stack[len(stack)-1]] > heights[i]:
# 找到了比当前栈顶小的元素 则结束开始计算当前栈顶对应的面积
cur = stack[len(stack)-1]
stack.pop()
left = stack[len(stack)-1] + 1
right = i - 1
maxInt = max(maxInt,(right-left+1) * heights[cur])
stack.append(i)
return maxInt

if __name__ == '__main__':
s = Solution()
print(s.largestRectangleArea([2,1,5,6,2,3]))
StriveZs wechat
Hobby lead  creation, technology change world.