datetime:2024/2/28 10:24
author:nzb
滑动窗口-单调栈
非常重要，非常重要，非常重要
滑动窗口
窗口只能右边界或左边界向右滑的情况下，维持窗口内部最大值或者最小值快速更新的结构
窗口内最大值与最小值更新结构的原理与实现
- 由一个代表题目，引出一种结构(滑动窗口)
- 【题目】 有一个整型数组
arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。 例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时:
[4 3 5]4 3 3 6 7 窗口中最大值为5
4[3 5 4]3 3 6 7 窗口中最大值为5
4 3[5 4 3]3 6 7 窗口中最大值为5
4 3 5[4 3 3]6 7 窗口中最大值为4
4 3 5 4[3 3 6]7 窗口中最大值为6
4 3 5 4 3[3 6 7] 窗口中最大值为7
- 如果数组长度为
n，窗口大小为w，则一共产生n-w+1个窗口的最大值。 - 请实现一个函数。 输入:整型数组
arr，窗口大小为w。 - 输出:一个长度为
n-w+1的数组res，res[i]表示每一种窗口状态下的以本题为例，结果应该返回{5,5,5,4,6,7}。
from collections import deque
def get_max_window(arr, w):
if not arr or w < 1 or len(arr) < w:
return []
dq = deque()
res = [None] * (len(arr) - w + 1)
idx = 0
for i in range(len(arr)):
while dq and arr[dq[-1]] <= arr[i]: # 新元素大于等于尾部元素
dq.pop()
dq.append(i)
# i - w就是L的索引位置，如果索引位置等于双端队列的头元素，就要弹出, 过期下标
if dq[0] == i - w:
dq.popleft()
if i >= w - 1: # 到达窗口要求，更新窗口最大值
res[idx] = arr[dq[0]]
idx += 1
return res
print(get_max_window([4, 3, 5, 4, 3, 3, 6, 7], 3))
给定一个数组arr,给出数组中窗口的边界L和R，用最小代价求出数组L到R位置中的元素最大值(或最小值)。
思路分析
借用一个双端队列(头尾都可以进出)，队列只存储数组中元素的索引，不断滑动更新窗口，调正双端队列中元素的值，使其永远保证从大到小的顺序(单调栈)(最大值，最小值的话保证从小到大的顺序)。
- 如果数组的右指针向右移动，则将元素按照添加条件(双端队列为空或小于尾部元素)添加到双端队列尾部。
- 这个如果待添加的元素
>=双端队列尾部的值，则不断弹出队列尾部元素(弹出的元素，永远的丢弃了)，直到满足由大到小的条件，注意相等也要弹出 - 如果数组的左指针向右移动，则检查队列头索引与当前左指针是否一致，如果一致则弹出。
任何一个时刻，窗口最大的值都是双端队列的头部元素
复杂度： - 时间复杂度：
O(N)，注意虽然是两层循环，但元素只从滑动窗口尾部进，从头部清除，只是顺序扫描了一遍，每个元素都只进出队列一次，总的平均代价O(1)。 - 空间复杂度：O(N)，这里利用两个滑动窗口分别保存最大值和最小值。- 双端队列维持的是什么信息
- 比如
[6, 5, 4, 3] 5 7，双端队列为[0, 1, 2, 3]，如果目前窗口不再往右扩，而只移动L，维持了谁会依次成为最大值这个信息 - 如果
R再右移下，为啥4位置的5进来以后，前面的5,4,3都要弹出，因为下标比他们晚过期，值还比他们大，他们再也不可能成为最大值，相等也一样，因为下标晚，意味着过期晚
- 比如
from collections import deque
class WindowMax(object):
"""黑盒，用户自己调"""
def __init__(self, arr):
self.L = -1
self.R = 0
self.arr = arr
self.dq = deque()
def add_num_from_right(self):
if self.R == len(self.arr):
return
while self.dq and self.arr[self.dq[-1]] <= self.arr[self.R]:
self.dq.pop()
self.dq.append(self.R)
self.R += 1
def remove_num_from_left(self):
if self.L >= self.R - 1: # 窗口形成，不移除
return
self.L += 1
if self.dq[0] == self.L:
self.dq.popleft()
def get_max(self):
if not self.dq:
return self.arr[self.dq[0]]
return None
单调栈
在数组中想找到一个数，左边和右边比这个数小(或大)、且离这个数最近的位置。如果对每一个数都想求这样的信息，能不能整体代价达到O(N)？需要使用到单调栈结构单调栈结构的原理和实现
- 如果你要找左边右边最近比你大的，栈的顺序从下往上应该是大->小
- 如果你要找左边右边最近比你小的，栈的顺序从下往上应该是小->大
idx = 0 1 2 3 4 5 6
arr = 5 4 3 6 1 2 0
- 对于无重复的数组
- 0索引入栈,
[0] 4<5，1索引入栈，[0, 1]3<4，2索引入栈，[0, 1, 2]6>3，不满足单调栈结构，弹出索引2，右边比他大的是6，左边比他大的的栈的下一个元素4，[0, 1]6>4，不满足单调栈结构，继续弹出索引1，右边比他大的是6，左边比他大的的栈的下一个元素5，[0]6>4，不满足单调栈结构，继续弹出索引0，右边比他大的是6，左边比他大的的栈的下一个元素没有，[]- 索引3入栈，
[3] 1<6：索引4入栈，[3,4]2>1：弹出索引4，左->6，右->2，索引5入栈，[3, 5]0<6：索引6入栈，[3, 5, 6]- 遍历完后，此时栈里元素还有
[3,5,6]，进入清算阶段， 分别弹出，左->下一个元素(索引3没有)，右无
- 0索引入栈,
idx = 0 1 2 3 4 5 6 7
arr = 5 4 3 4 5 3 5 6
- 对于有重复的数组 ，单个索引变成一个索引链表(或索引数组)
- 0索引入栈，
[0] 4<5，1索引入栈，[0, 1]3<4，2索引入栈，[0, 1, 2]4>3，弹出索引2结算，右边->4，左边->4，索引3入栈，因为相等跟1压在一起，[[0], [1,3]]5>4，依次弹出[1,3], 1位置，左->下一个元素最右的0位置的5，右->4位置的5，接着3位置，左->下一个元素最右的0位置的5，右->4位置的5，4入栈压一起，[[0, 4]]3<5，5索引入栈，[[0, 4], 5]5>3，不满足单调栈结构，继续弹出索引5，右边->下一个元素最右的4位置的5，左边->5，索引6入栈压一起，[[0, 4, 6]]6>5：依次弹出[0, 4, 6], 左->无，右->6，7入栈，[[7]]- 遍历完后，此时栈里元素还有
[[7]]，进入清算阶段， 分别弹出，左->没有，右->没有
- 0索引入栈，
由于每个数都是进栈一次出栈一次，所以复杂度为O(N)。
import typing
class MonotonousStack(object):
@staticmethod
def get_near_less_no_repeat(arr):
"""获取左右比他小的元素，无重复值"""
res = [[typing.Any, typing.Any] for _ in range(len(arr))] # 左，右
stack = []
for i in range(len(arr)):
while stack and arr[stack[-1]] > arr[i]:
# 保持单调性，不满足的时候弹出，结算弹出元素
idx = stack.pop()
left_less = stack[-1] if stack else None
res[idx][0] = left_less
res[idx][1] = i
stack.append(i)
# 清算
while stack:
idx = stack.pop()
left_less = stack[-1] if stack else None
res[idx][0] = left_less
res[idx][1] = None
return res
@staticmethod
def get_near_less_repeat(arr):
"""获取左右比他小的元素，有重复值"""
res = [[typing.Any, typing.Any] for _ in range(len(arr))] # 左，右
stack = [] # [[0,1], [2]]
for i in range(len(arr)):
while stack and arr[stack[-1][-1]] > arr[i]:
# 保持单调性，不满足的时候弹出，结算弹出元素
idx_list = stack.pop() # 取最后一个元素索引
# 取位于下面位置的列表中，最晚加入的那个索引
left_less = stack[-1][-1] if stack else None
for idx in idx_list:
res[idx][0] = left_less
res[idx][1] = i
if stack and arr[stack[-1][-1]] == arr[i]:
stack[-1].append(i)
else:
stack.append([i])
# 清算栈内元素
while stack:
idx_list = stack.pop()
# 清算索引元素
# 取位于下面位置的列表中，最晚加入的那个索引
left_less = stack[-1][-1] if stack else None
for idx in idx_list:
res[idx][0] = left_less
res[idx][1] = None
return res
print(MonotonousStack().get_near_less_no_repeat([5, 4, 3, 6, 1, 2, 0]))
print(MonotonousStack().get_near_less_repeat([5, 4, 3, 4, 5, 3, 5, 6]))
# [[None, 1], [None, 2], [None, 4], [2, 4], [None, 6], [4, 6], [None, None]]
# [[None, 1], [None, 2], [None, None], [2, 5], [3, 5], [None, None], [5, None], [6, None]]
单调栈题目
定义：正数数组中累积和与最小值的乘积，假设叫做指标A。给定一个数组，请返回子数组中，指标A最大的值。
[5, 3, 2, 1, 6, 7, 8, 4]- 遍历每个元素，以当前元素为最小值，往左右两边扩，不能比当前元素小的范围
比如
- 5可能为
[5] - 3可能为
[5, 3],[3] - 2可能为
[5, 3, 2],[3, 2],[2] - 等等，就是单调栈，找到左右两边最近比他小的就是不能扩进去的位置
- 5可能为
TODO 有问题
def get_sub_arr_max(arr):
size = len(arr)
sums = [0]
for i in range(1, size):
sums.append(arr[i - 1] + arr[i])
max_val = float("-inf")
stack = []
for i in range(size):
while stack and arr[stack[-1]] >= arr[i]:
idx = stack.pop()
prev_sum = sums[i - 1] - sums[stack[-1]] if stack else sums[i - 1]
max_val = max(max_val, prev_sum * arr[idx])
stack.append(i)
while stack:
idx = stack.pop()
prev_sum = sums[-1] - sums[stack[-1]] if stack else sums[-1]
max_val = max(max_val, prev_sum * arr[idx])
return max_val
data = [5, 3, 2, 1, 6, 7, 8, 4]
print(get_sub_arr_max(data))