如题,我们要建立结构体
S
t
o
c
k
S
p
a
n
n
e
r
StockSpanner
StockSpanner和单调栈。我们有两种选择:
S
t
o
c
k
S
p
a
n
n
e
r
StockSpanner
StockSpanner存储
p
r
i
c
e
price
price和
p
o
s
pos
pos。那么我们要用数组模拟栈。栈的大小必须给定,空间复杂度太高。
S
t
o
c
k
S
p
a
n
n
e
r
StockSpanner
StockSpanner存储
s
t
a
c
k
stack
stack链表和
i
d
x
idx
idx当前位置。链表存储
p
r
i
c
e
price
price和
p
o
s
pos
pos和
n
e
x
t
next
next,用链表模拟栈。可以动态申请空间,较灵活。
博主使用链表模拟栈,即第
2
2
2种。
四、代码分析
理解思路重要!
欢迎读者在评论区留言,作为日更博主,看到就会回复的。
五、AC
六、复杂度分析
时间复杂度:
O
(
n
)
O(n)
O(n) ,
n
n
n是调用
n
e
x
t
next
next函数的次数。
空间复杂度:
O
(
n
)
O(n)
O(n),如果股票价格降序排列,栈内最终会有
n
n
n个数,最坏空间复杂度
O
(
n
)
O(n)
O(n)。