在滑动 window 的倒数第二个测试用例中获取 TLE（使用队列）

Question

这是我花了将近 2 天时间解决的 Leetcode 问题。

https://leetcode.com/problems/sliding-window-maximum/

我已经能够通过 59/61 个测试用例，但我在第 60 个测试用例中获得了 TLE。你能否建议我是否可以在某个地方调整我的程序以通过所有测试用例？

我使用的方法如下： slide 是一个列表，由给定时间幻灯片中的所有元素组成。当幻灯片向右滑动一个位置时，前面的元素被弹出，我们每次都必须检查最大元素。但是如果我们检查 max 元素是否真的被弹出，则可以节省时间。如果弹出的不是最大元素，我们只需要将最大元素与新添加的元素与 window 进行比较并将其添加到答案中即可。但是，如果它确实是最大元素，我们就必须再次找到最大元素。通过上述方法，我可以通过 59/61 个案例。

然后我想：

max 元素可能出现在幻灯片中的多个位置。因此，我最初从幻灯片中当前的所有元素创建了一个集合，然后找到了最大元素，这可能有助于节省时间，但这也无济于事。这是我试过的代码：

class Solution(object):
def maxSlidingWindow(self, nums, k):
    slide = list()
    answer = list()
    lennums = len(nums)-1
    if k==len(nums):
        answer.append(max(nums))
    else:
        
        for i in range(0,k):
            slide.append(nums[i])
        flag =1
        new=0
        while k<=lennums:
            
            if flag==1: #meaning the max eleemnt has been popped off. so we have to find the new max element again
                if slide[0]!=new:
                    new = max(slide)
                else:
                    new =new
                
                answer.append(new)#new has the value of max element in the slide
            else: #the element popped off was not the max element
                if new > slide[len(slide)-1]:
                    
                    answer.append(new)
                else:
                    answer.append(slide[len(slide)-1])
                    new = slide[len(slide)-1]
                
            
            
            popped = slide.pop(0)
            if popped==new :
                flag=1
            else :
                flag=0
                
            slide.append(nums[k])
            k = k+1
       
        slide.append(nums[len(nums)-1])
        answer.append(max(slide))
    return answer

Answer 1

让我们使用一个双端队列 （双端队列），结构从相同的O弹出/推到任一侧(1) 性能。

存储在双端队列索引而不是元素中更方便，因为两者都在数组解析期间使用。一旦你意识到这一点，就会很自然地以不同的 que 方式来处理这个问题。

[注意]类似的想法已经在很多论坛上讨论过了，应该分享给“社区”。

算法

会涉及到这些步骤：

分别处理前k个元素以启动双端队列。遍历数组。每一步：

清理双端队列：

只保留当前滑动的元素索引window。删除所有小于当前元素的索引，因为它们不会是最大的。

将当前元素附加到双端队列。将 deque[0] 附加到输出。 Return 输出数组。

# Implementation  - Leave as an exercise
# from collections import deque

在滑动 window 的倒数第二个测试用例中获取 TLE（使用队列）

Getting TLE in second last test case of sliding window (used queues)

python

algorithm

queue