for i in range(len(nums)):
while stack and nums[i]>=stack.top():
stack.pop()
stack.push()
单调栈的作用
- 以
O
(
n
)
O(n)
O(n)时间复杂度求出某个数的左边或右边第一个比它大或小的元素。
1. 求第
i
i
i 个数左边第一个比它小的元素的位置
- 从左到右遍历元素构造单增栈：一个元素左边第一个比它小的数的位置就是将它插入单增栈时栈顶元素的值，若栈为空，则说明不存在这么一个数。
举例来说，
n
u
m
s
=
[
5
,
4
,
3
,
4
,
5
]
nums=[5,4,3,4,5]
nums=[5,4,3,4,5]，初始时栈空
s
t
a
c
k
=
[
]
stack=[]
stack=[]
-
i
=
1
i=1
i=1：栈空，左边没有比它小的元素，故
L
[
1
]
=
0
L[1]=0
L[1]=0，同时下标 1 入栈，
s
t
a
c
k
=
[
1
]
stack=[1]
stack=[1]；
-
i
=
2
i=2
i=2：当前元素 4 小于栈顶元素对应的元素 5，故将 1 弹出栈，此时栈空，故
L
[
2
]
=
0
L[2]=0
L[2]=0，然后将元素 4 对应的位置下标 2 入栈，
s
t
a
c
k
=
[
2
]
stack=[2]
stack=[2]；
-
i
=
3
i=3
i=3：当前元素 3 小于栈顶元素对应的元素 4，故将 2 弹出栈，此时栈空，故
L
[
3
]
=
0
L[3]=0
L[3]=0，然后将元素 3 对应的位置下标 3 入栈，
s
t
a
c
k
=
[
3
]
stack=[3]
stack=[3]；
-
i
=
4
i=4
i=4：当前元素 4 大于栈顶元素对应的元素 3，故
L
[
4
]
=
s
t
a
c
k
.
t
o
p
(
)
=
3
L[4]=stack.top()=3
L[4]=stack.top()=3，同时将元素 4 对应的下标 4 入栈，
s
t
a
c
k
=
[
3
,
4
]
stack=[3,4]
stack=[3,4]；
-
i
=
5
i=5
i=5：当前元素 5 大于栈顶元素对应的元素 4，故
L
[
5
]
=
s
t
a
c
k
.
t
o
p
(
)
=
4
L[5]=stack.top()=4
L[5]=stack.top()=4，同时将元素 5 对应的下标 5 入栈，
s
t
a
c
k
=
[
3
,
4
,
5
]
stack=[3,4,5]
stack=[3,4,5]。
2. 求第
i
i
i 个数左边第一个比它大的元素的位置
- 从左到右遍历元素构造单减栈：一个元素左边第一个比它大的数的位置就是将它插入单减栈时栈顶元素的值，若栈为空，则说明不存在这么一个数。
3. 求第
i
i
i 个数右边第一个比它小的元素的位置
- 从右到左遍历元素构造单增栈：一个元素右边第一个比它小的数的位置就是将它插入单增栈时栈顶元素的值，若栈为空，则说明不存在这么一个数。
- 从左到右遍历元素构造单增栈：一个元素右边第一个比它小的数的位置就是将它弹出栈时即将入栈的元素的下标，如果没被弹出栈，说明不存在这么一个数。
举例来说，
n
u
m
s
=
[
5
,
4
,
3
,
4
,
5
]
nums=[5,4,3,4,5]
nums=[5,4,3,4,5]，初始时栈空
s
t
a
c
k
=
[
]
stack=[]
stack=[]
-
i
=
1
i=1
i=1：栈空，下标1 入栈，
s
t
a
c
k
=
[
1
]
stack=[1]
stack=[1]；
-
i
=
2
i=2
i=
