公众号文章地址：https://mp.weixin.qq.com/s/_wqX3Bir3zTuRbzKh6sHXA
题一：
题目：
给定一个数组 list 和一个数字 w ，要求获取 list 中滑动窗口为 w 的最大值
分析：
构建一个双端队列获取最大值，从头部到尾部保证从大到小的顺序，则可获得当前窗
口的最大值（队列头部第一个数），往双端队列里面加数的逻辑：
当前数和双端队列的尾部的数进行比较，
while 当前数 > 双端队列的尾部的数 or len(双端队列) > 0 :
则将尾部的数进行弹出
双端队列.append(当前数)
这么做为什么会有效呢？因为这样构建出来的双端队列头部的数字有如下两个特性：
1.数值是最大的
2.比弹出的数晚过期（下标index大） 代码实现：
def get_max_value_from_window(self,arr:list,win_len:int):
q_max = deque()
print(f"arr:{arr}")
print(f"win_len:{win_len}")
if len(arr) < win_len :
return None
res = []
for i in range(0,len(arr)):
while q_max.__len__() > 0 and arr[q_max[-1]] < arr[i] :
q_max.pop()
q_max.append(i)
#
if i >= win_len-1 and q_max[0] <= i - win_len:
# 剔除窗口外失效的值
q_max.popleft()
if i >= win_len-1:
res.append(arr[q_max[0]])
return res 结果输出：
输入arr:[2, 4, 5, 5, 4, 3, 8, 55, 6, 3, 9, 1]
输入win_len:4
输出:[5, 5, 5, 8, 55, 55, 55, 55, 9] 题二：
time: 01:04:23
题目：
给定一个整型数组arr,和一个整数num,某个arr中的子数组sub,如果想达标，
必须满足：
sub中最大值 - sub中最小值 <= num ,
返回arr中达标子数组的数量
分析：
sub = arr[L:R] 若sub是满足上述条件的数组，
当L和R往里缩时，形成新的数组都满足上述条件，
当L和R往外扩时，形成新的数组都不满足上述条件 代码实现：
def get_sub_arr_num(self,arr,num):
print(title)
print(f"输入 arr：{arr},num:{num}")
res = 0
L = 0
R = 0
q_max = deque()
q_min = deque()
while L < arr.__len__():
while R < arr.__len__():
while q_max.__len__() != 0 and arr[q_max[-1]] <= arr[R]:
# 如果 q_max 不为空，并且q_max中最后一个的值 < arr[i] ,则进行右弹出
q_max.pop()
# 弹出完之后 ，将新数据加入 q_max
q_max.append(R)
while q_min.__len__() != 0 and arr[q_min[-1]] >= arr[R]:
# 如果 q_min 不为空，并且 q_min 中最后一个的值 < arr[i] ,则进行右弹出
q_min.pop()
# 弹出完之后 ，将新数据加入 q_min
q_min.append(R)
if q_max.__len__() > 0 and q_max[0] < L :
q_max.popleft()
if q_min.__len__() > 0 and q_min[0] < L :
q_min.popleft()
if arr[q_max[0]] - arr[q_min[0]] > num:
cnt = len(arr[L:R]) - 1
res += cnt
print(f"R:{R},L:{L},R-L:{R-L}\t",arr[L:R],cnt)
break
R += 1
L += 1
return res 结果输出：
输入 arr：[2, 4, 5, 5, 4, 3, 8, 55, 6, 3, 9, 1],num:4
输出：16 题三：
获取数组中的每个值，左边离它最近且值比它小的下标，没有则为-1
右边离它最近且值比它小的下标，没有则为-1 代码实现：
def get_closed_min(self,arr):
"""获取数组中的每个值，左边离它最近且值比它小的下标，没有则为-1
右边离它最近且值比它小的下标，没有则为-1
"""
print("输入：",arr)
res = []
que = deque() # 栈内维持由小到大的单调性
if len(arr) == len(set(arr)):
"说明数组中没有重复值"
for i in range(0,len(arr)):
if que.__len__() != 0 :
if que.__len__() > 0 and que[-1] > arr[i] :
while que.__len__() and que[-1] > arr[i]:
# 说明 arr[i] 是 que[-1] 右边比它小的值中离它最近的值
r_min = arr[i]
cur = que.pop()
if que.__len__() > 0 :
# 弹出后，如果栈中还有值，说明栈弹出的第一个值是 cur 左边比它小的值中离它最近的值
l_min = que[-1]
else:
l_min = -1
res.append([cur,l_min,r_min])
que.append(arr[i])
while que.__len__() != 0:
cur = que.pop()
r_min = -1
if que.__len__() > 0:
# 弹出后，如果栈中还有值，说明栈弹出的第一个值是 cur 左边比它小的值中离它最近的值
l_min = que[-1]
else:
l_min = -1
res.append([cur,l_min,r_min])
return res
else:
"说明数组中有重复值"
for i in range(0,len(arr)):
if que.__len__() != 0 :
if que.__len__() > 0 and arr[que[-1][-1]] > arr[i] :
while que.__len__() and arr[que[-1][-1]] > arr[i]:
# 说明 arr[i] 是 que[-1] 右边比它小的值中离它最近的值
r_min = i
curs = que.pop()
for cur in curs:
if que.__len__() > 0 :
# 弹出后，如果栈中还有值，说明栈弹出的第一个值是 cur 左边比它小的值中离它最近的值
l_min = que[-1][-1]
else:
l_min = -1
res.append([cur,l_min,r_min])
else:
if arr[que[-1][-1]] == arr[i]:
tmp = que.pop()
tmp.append(i)
que.append(tmp)
continue
if que.__len__() > 0 and arr[que[-1][-1]] == arr[i]:
tmp = que.pop()
tmp.append(i)
que.append(tmp)
else:
que.append([i])
while que.__len__() != 0:
curs = que.pop()
for cur in curs:
r_min = -1
if que.__len__() > 0:
# 弹出后，如果栈中还有值，说明栈弹出的第一个值是 cur 左边比它小的值中离它最近的值
l_min = que[-1][-1]
else:
l_min = -1
res.append([cur,l_min,r_min])
return res 结果输出：
输入：[2, 4, 5, 5, 4, 3, 8, 55, 6, 3, 9, 1]
输出：[[2, 1, 4], [3, 1, 4], [1, 0, 5], [4, 0, 5], [7, 6, 8], [6, 5, 8], [8, 5, 9], [10, 9, 11], [5, 0, 11], [9, 0, 11], [0, -1, 11], [11, -1, -1]] 题四：
题目：
给定一个只包含正整数的数组arr,arr中任何一个子数组sub,一定都可以算出
value =（sub累加和）*（sub中的最小值）,那么，在所有子数组中，最大的
value是多少
分析：
以arr[i]为子数组sub的最小值往数组arr左右两边扩充，使得len(sub)最大，
则可以获得 以arr[i]为最小值的子数组sub，使得value最大,可以使用
get_closed_min 中的结果，来获取sub的最大边界（以arr[i]为最小值） 代码实现
def get_max_value(self,arr):
"""
题目：
给定一个只包含正整数的数组arr,arr中任何一个子数组sub,一定都可以算出 value =（sub累加和）*（sub中的最小值）,
那么，在所有子数组中，最大的value是多少
分析：
以arr[i]为子数组sub的最小值往数组arr左右两边扩充，使得len(sub)最大，则可以获得 以arr[i]为最小值的子数组sub，使得value最大
可以使用get_closed_min 中的结果，来获取sub的最大边界（以arr[i]为最小值）
"""
res = []
close_value = obj.get_closed_min(arr)
# print(len(arr),len(res))
close_value = sorted(close_value, key=lambda x: x[0])
for tmp in close_value:
# print(tmp)
index = tmp[0]
# 因为get_closed_min 获取的是左右两边比 arr[i] 小而且离离 arr[i] 最近值的下标，故所以要把这两个值剔除掉，又因为python数组切片左闭右开的特性，故right要+1
left = tmp[1]+1
right = tmp[2]+1-1
if left <= -1:
left = index
if right <= -1 :
right = index
# print(tmp)
value = arr[index]*sum(arr[left:right])
# print(arr[index],arr[left:right],value)
res.append(value)
max_value = max(res)
return max_value 结果输出：
输入： [2, 4, 5, 5, 4, 3, 8, 55, 6, 3, 9, 1]
输出：3025 总结：单调栈和窗口都是利用结构内有序 和 新进来的数的下标比结构内的数的下标更晚过期的特性。
![树的基本概念(定义、基本术语、性质)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)