查找给定大小的每个连续子数组的最大值 [英] Finding the max of each continguous subarray of a given size

问题描述

我正在尝试在Python中解决以下问题

给出一个数组和一个整数k，为每个和每个大小为k的连续子数组。

这个想法是使用双端队列。这是我的代码：

  def diff_sliding_window（arr，win）：
＃max = -inf 
 Q = [] 
 win_maxes = [] i在range（win）中的每个窗口的最大值
：
 print（Q）
而len（Q）> 0并且arr [i]> = arr [len（Q）-1]：
＃删除较小元素
的索引Q.pop（）＃删除最后一个元素
 Q.append（i）
＃print（'>>'，Q）
 
 for i in range（win，len（arr））：
＃win_maxes。 append（arr [Q [0]]）
 print（arr [Q [0]]）
而len（Q）> 0和Q [0]< = i-获胜：
 Q.pop（）
而len（Q）> 0并且arr [i]> = arr [len（Q）-1]：
 Q.pop（0）
 Q.append（i）
＃win_maxes.append（arr [ Q [0]]）
 
打印（arr [Q [0]]）
  

但是我无法弄清楚测试用例的原因：

  t1 = [1、3，-1， -3、5、3、6、7] 
 t2 = [12、1、78、90、57、89、56] 
  

我没有得到正确的结果。

---

更新：

我已经进行了Matt Timmermans建议的更改，但仍无法获得正确的输出。对于 t2 ，并且 win = 3

  78 
 90 
 90 
 89 <---应该是90 
 89 
  

这是我更新后的代码：

 来自收藏集import deque 
 
 def diff_sliding_window（arr，win）：
＃max = -inf 
 Q = deque（）
 win_maxes = []＃每个窗口的最大值
对于范围内的我（win）：
＃print（Q）
而len（Q）> 0并且arr [i]> = arr [Q [len（Q）-1]]：
＃删除较小元素的索引
 Q.pop（）＃删除最后一个元素
 Q.append（i）
＃print（'>>'，Q）
 
 for i in range（win，len（arr））：
 ＃win_maxes.append（arr [Q [0]]）
 print（arr [Q [0]]）
而len（Q）> 0和Q [0]< = i-获胜：
 Q.pop（）
而len（Q）> 0并且arr [i]> = arr [Q [len（Q）-1]]：
 Q.popleft（）
 Q.append（i）
 
 
 print（arr [Q [0]]）
  

解决方案

似乎您正在尝试针对此问题实施O（n）算法，这比此时的其他两个答案要好。

但是，您的实现不正确。当您说 arr [i]> = arr [len（Q）-1] 时，您应该说 arr [i]> = arr [Q [len（Q）-1]] 或 arr [i]> = arr [Q [-1]] 。您还可以在第二个循环中交换 pop 和 pop（0）案件。

尽管如此，您的算法也不是O（n），因为您使用了 Q .pop（0），这需要O（k）时间。因此，您的总运行时间为O（kn）。在 Q 中使用双端队列可以解决此问题。

此处已全部修复，并有一些注释说明了如何解决此问题。作品：

 从收藏中进口deque 
 
 def diff_sliding_window（arr，win）：
 
，如果获胜> len（arr）：
 return [] 
 
 win_maxes = []每个窗口的最大值
 
 #Q包含窗口中大于项的索引
＃它们右边的所有项目。它始终包括窗口
中的最后一项
＃Q = deque（）
 
 #fill初始窗口中的Q 
 for range（win）中的i：
＃在len（Q）>删除不大于新项目
的所有内容。 0并且arr [i]> = arr [Q [-1]]：
 Q.pop（）
 Q.append（i）
 
 win_maxes.append（arr [Q [0]]）
 
 for i在范围（win，len（arr））：
＃删除窗口
左边的索引（最多1个，实际上） len（Q）> 0 and Q [0]< =（i-win）：
 Q.popleft（）
 
＃在len时删除不大于新项目
的任何内容（Q）> 0并且arr [i]> = arr [Q [-1]]：
 Q.pop（）
 Q.append（i）
 win_maxes.append（arr [Q [0 ]]）
 
 return win_maxes 
  

尝试一下： https://ideone.com/kQ1qsQ

证明这是O（ N）：内部循环的每次迭代都会从Q中删除一个项目。由于总共只添加了 len（arr），因此最多可以有 len（arr）内循环的总次迭代。

I'm trying to solve the following problem in Python

Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.

The idea is to use a double ended queue. This is my code:

def diff_sliding_window(arr, win):
#     max = -inf
    Q = []
    win_maxes = [] # max of each window
    for i in range(win):
        print(Q)
        while len(Q) > 0 and arr[i] >= arr[len(Q) - 1]:
            # get rid of the index of the smaller element
            Q.pop() # removes last element
        Q.append(i)
#     print('>>', Q)

    for i in range(win, len(arr)):
#         win_maxes.append(arr[Q[0]])
        print(arr[Q[0]])
        while len(Q) > 0 and Q[0] <= i - win:
            Q.pop()
        while len(Q) > 0 and arr[i] >= arr[len(Q)-1]:
            Q.pop(0)
        Q.append(i)
#     win_maxes.append(arr[Q[0]])

    print(arr[Q[0]])

But I can't figure out why for the test cases:

t1 = [1, 3, -1, -3, 5, 3, 6, 7]
t2 = [12, 1, 78, 90, 57, 89, 56]

that I'm not getting the correct results.

---

Update:

I've made the changes that Matt Timmermans suggested, but I'm still not obtaining the proper output. For t2, and win = 3

78
90
90
89 <--- should be 90
89

Here is my updated code:

from collections import deque

def diff_sliding_window(arr, win):
#     max = -inf
    Q = deque()
    win_maxes = [] # max of each window
    for i in range(win):
#         print(Q)
        while len(Q) > 0 and arr[i] >= arr[Q[len(Q)-1]]:
            # get rid of the index of the smaller element
            Q.pop() # removes last element
        Q.append(i)
#     print('>>', Q)

    for i in range(win, len(arr)):
#         win_maxes.append(arr[Q[0]])
        print(arr[Q[0]])
        while len(Q) > 0 and Q[0] <= i - win:
            Q.pop()
        while len(Q) > 0 and arr[i] >= arr[Q[len(Q)-1]]:
            Q.popleft()
        Q.append(i)


    print(arr[Q[0]])

解决方案

It looks like you are trying to implement the O(n) algorithm for this problem, which would be better than the other two answers here at this time.

But, your implementation is incorrect. Where you say arr[i] >= arr[len(Q)-1], you should say arr[i] >= arr[Q[len(Q)-1]] or arr[i] >= arr[Q[-1]]. You also swapped the pop and pop(0) cases in the second loop. It looks like it will be correct after you fix those.

Also, though, your algorithm is not O(n), because you using Q.pop(0), which takes O(k) time. Your total running time is therefore O(kn) instead. Using a deque for Q will fix this.

Here it is all fixed, with some comments to show how it works:

from collections import deque

def diff_sliding_window(arr, win):

    if win > len(arr):
        return []

    win_maxes = [] # max of each window

    #Q contains indexes of items in the window that are greater than
    #all items to the right of them.  This always includes the last item
    #in the window
    Q = deque()

    #fill Q for initial window
    for i in range(win):
        #remove anything that isn't greater than the new item
        while len(Q) > 0 and arr[i] >= arr[Q[-1]]:
            Q.pop()
        Q.append(i)

    win_maxes.append(arr[Q[0]])

    for i in range(win, len(arr)):
        #remove indexes (at most 1, really) left of window
        while len(Q) > 0 and Q[0] <= (i-win):
            Q.popleft()

        #remove anything that isn't greater than the new item
        while len(Q) > 0 and arr[i] >= arr[Q[-1]]:
            Q.pop()
        Q.append(i)
        win_maxes.append(arr[Q[0]])

    return win_maxes

try it: https://ideone.com/kQ1qsQ

Proof that this is O(N): Each iteration of the inner loops removes an item from Q. Since there are only len(arr) added to Q in total, there can be at most len(arr) total iterations of the inner loops.

这篇关于查找给定大小的每个连续子数组的最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！