131. 直方图中最大的矩形
摘要
Title: 131. 直方图中最大的矩形
Tag: 单调栈
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
131. 直方图中最大的矩形
-
题意
-
思路
单调栈典型的应用题
具体思路为，枚举每个高度，找到此高度往左和往右延申的最长长度，两者相乘就是答案
优化思路就是用单调栈实现的，此高度延申的边界就是比它小的高度，那么就是要找左边第一个小的，和右边第一个小的，(l,r)便是此高度能延伸的
注意
- 为了方便处理边界，两侧边界都为-1，即比最小的高度还小
- 此次栈存的是下标，所以栈的初始值是0或者n+1
-
代码
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'''
Author: NEFU AB-IN
Date: 2022-02-27 09:19:29
FilePath: \ACM\Acwing\131.py
LastEditTime: 2022-02-27 09:52:36
'''
N = int(1e5 + 100)
h, l, r = [0] * N, [0] * N, [0] * N
while True:
try:
h = list(map(int, input().split()))[1:]
if not h:
break
n = len(h)
h = [-1, *h, -1]
# 此次栈存的是下标，比较时换成下标比较即可
stk = [0]
for i in range(1, n + 1):
while stk and h[stk[-1]] >= h[i]:
stk.pop()
l[i] = stk[-1] if stk else -1
stk.append(i)
stk = [n + 1]
for i in range(n, -1, -1):
while stk and h[stk[-1]] >= h[i]:
stk.pop()
r[i] = stk[-1] if stk else -1
stk.append(i)
res = 0
for i in range(1, n + 1):
res = max(res, h[i] * (r[i] - l[i] - 1))
print(res)
except:
break
