LeetCode 239 Sliding Window Maximum

Posted on | In | 阅读

单调队列

设置一个双向队列，按顺序将数组的下标push到队列尾，保证下标的升序，每次都检查队列头的下标是否超出了窗口，超出则pop队列头。

另外push新的下标前，要将之前下标中存储的数比自己小的pop掉。这样就能够保证所有下标对应的数是降序的。每次论队列头就是当前窗口中最大的数。

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n % 2 == 0:
            half = n // 2
        else:
            half = n // 2 + 1
        cnt = {}
        for i in range(n):
            if not cnt.has_key(nums[i]):
                cnt[nums[i]] = 1
            else:
                cnt[nums[i]] += 1
            if cnt[nums[i]] >= half:
                return nums[i]