数据结构篇-单调栈和窗口及其更新结构

公众号文章地址：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

总结：单调栈和窗口都是利用结构内有序 和 新进来的数的下标比结构内的数的下标更晚过期的特性。