Python 中的滑动窗口中值两堆方法，TLE 错误

Question

我在使用两个堆方法解决滑动窗口中值问题时遇到困难，因为我在 K = 50000 且输入 100000 个整数的数组的测试用例上不断遇到时间限制超出错误。有没有办法降低代码的时间复杂度？

问题：

给定一个整数数组 nums 和一个整数 k。有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。窗口中只能看到k个数字。滑动窗口每向右移动一个位置。

返回原始数组中每个窗口的中值数组。

我的解决方案：

class Solution(object):

 def __init__(self):
     self.small = [] #max heap of small numbers
     self.large = [] #min heap of large numbers
     
 def balance(self):
     #if small bigger than large by more than 1, pop and push
     if len(self.small) > len(self.large) + 1:
         val = heapq.heappop(self.small) *-1
         heapq.heappush(self.large,val)
     if len(self.large) > len(self.small) + 1:
         val = heapq.heappop(self.large)
         heapq.heappush(self.small,val * -1)

 def addNum(self, num):
     heapq.heappush(self.small, -1 * num)

     #if max of small is greater than min of large, pop from small and push to large
     if (self.small and self.large and (-1 * self.small[0]) > self.large[0]):
         val = heapq.heappop(self.small) * -1
         heapq.heappush(self.large,val)
     
     self.balance()
     
 def findMedian(self):
     if len(self.small) > len(self.large):
         return self.small[0] * -1
     if len(self.large) > len(self.small):
         return self.large[0]
     
     
     result = float( ((self.small[0]*-1) + self.large[0])/2.0)
     return result
 
 def popNum(self,num):
     if num > (self.small[0] * -1):
         self.large.remove(num)
         heapq.heapify(self.large)
     else:
         self.small.remove(num * -1)
         heapq.heapify(self.small)
     
     self.balance()

 def medianSlidingWindow(self, nums, k):
     """
     :type nums: List[int]
     :type k: int
     :rtype: List[float]
     """
     
     start = 0
     end = len(nums) - k + 1
     result = []

     for i in range(start,start + k):
         self.addNum(nums[i])


     while start < end:
         
         median = self.findMedian()
         result.append(median)
         self.popNum(nums[start])
         if start < end - 1:
             self.addNum(nums[start + k])
         start += 1

     return result

Answer 1

主要的效率问题在于

popNum

，因为在那里你无法从堆的高效方法中获益。它使用

remove

搜索列表以找到一个条目，将其从列表中删除，从而破坏了堆一致性，因此您需要调用

heapify

。这使得移除操作的时间复杂度为 O(𝑘)，随着 𝑘 变大，这将开始造成伤害。

至少有两种解决方案：

• 使用堆实现可以删除复杂度为 O(log𝑘) 的元素（其中 𝑘 是堆的大小）。您可以通过维护一个哈希映射 (dict) 来实现此目的，该哈希映射将每个值映射到堆列表中的索引。获得索引后，您可以将该值替换为堆中的最后一个条目（缩短堆），并应用通常的筛选过程。但这一切意味着您需要控制堆的筛选操作，您将重写

  heapq

  函数。

• 仅标记已删除的元素，但将它们保留在堆中。在查看/弹出堆根时，识别是否有已删除标记，如果有，则弹出它，忽略它并重复。

  为了唯一标识元素，我们可以将它们与它们在输入列表中出现的索引连接起来，因为可能存在重复值。这样我们就为输入中的每个条目都有一个唯一的元组。在这个特定问题中，将它们标记为已删除很容易：如果索引位于当前窗口之外，则应将其视为已删除。这样我们只需移动窗口即可将元素隐式标记为已删除。

我选择了第二种选择。

为了处理（值，索引）元组，以及仍在堆中删除的元素，创建一个堆类可能是有意义的——它仍然可以依赖于

heapq

。

这是上述想法的实现。正如我注意到您使用的是 Python 2 而不是 Python 3 的 LeetCode 模板，下面有一个带参数的

super

调用，但在运行 Python 3 时可以省略这些参数：

import heapq

class MinWindowHeap(object):
    def __init__(self, conv=lambda x: x):
        self.heap = []
        self.conv = conv  # Conversion function (to negate values for MaxHeap)
        self.lowindex = 0  # lower index limit to identify deleted items
        
    def peek(self):  # Returns a (value, index) or None if the heap is empty
        while self.heap:
            item = self.conv(self.heap[0])
            if item[1] >= self.lowindex:
                return item
            # a deleted element: skip it
            heapq.heappop(self.heap)
    
    def push(self, item):
        heapq.heappush(self.heap, self.conv(item))
    
    def pop(self):
        item = self.peek()  # Remove deleted elements       
        heapq.heappop(self.heap)
        return item


def negate(item):  # Helper function for implementing MaxHeap
    return -item[0], item[1]


class MaxWindowHeap(MinWindowHeap):
    def __init__(self):
        # In Python 3 the arguments for super() can be omitted:
        super(MaxWindowHeap, self).__init__(negate)


class Solution(object):
    def rebalance(self, add):
        self.balance += add
        if abs(self.balance) < 2:
            return
        if self.balance > 1:
            self.small.push(self.large.pop())
        elif self.balance < -1:
            self.large.push(self.small.pop())
        self.balance = 0

    def insert(self, item):
        pivot = self.large.peek() or self.small.peek()
        islarge = not pivot or item > pivot
        heap = self.large if islarge else self.small
        heap.push(item)
        self.rebalance(1 if islarge else -1)
   
    def remove(self, item):
        pivot = self.large.peek()
        islarge = pivot and item >= pivot
        # We only adapt the window in order to mark the item as deleted
        self.large.lowindex = self.small.lowindex = item[1] + 1
        self.rebalance(-1 if islarge else 1)

    def getMedian(self):
        if self.balance == 0:
            return (self.large.peek()[0] + self.small.peek()[0]) * 0.5
        return self.large.peek()[0] if self.balance > 0 else self.small.peek()[0]

    def medianSlidingWindow(self, nums, k):
        self.small = MaxWindowHeap()
        self.large = MinWindowHeap()
        self.balance = 0
        # create list of (value, index) pairs
        items = [(val, i) for i, val in enumerate(nums)]
        for item in items[:k]:
            self.insert(item)
        lag = iter(items)  # iterator over the items to be removed
        result = [self.getMedian()]
        for item in items[k:]:
            self.remove(next(lag))
            self.insert(item)
            result.append(self.getMedian())

        return result