Day 13 单调|优先队列: 239. 滑窗最大值, 347. 前K高频, 215. 第K大, 4. 寻找两个正序数组的中位数

239. 滑动窗口最大值

• 思路
  • example
  • 手动实现单调队列 class
    • que = deque():　左边出，右边进或出
      • que 维护单调下降数列
        • 新加元素大于前面元素，可以把前面元素pop()，因为前面元素不可能成为当前或者下面窗口的最大值。
        • 新加元素小前面元素，append新元素即可。
    • size(que) = k，滑动窗口size = k
    • 每次需要 (先出后进）
      • 移除最左边元素
      • 加进当前位置元素
      • 取que[0]得到当前窗口最大值
• 复杂度. 时间：O(n), 空间: O(k)

单调队列：先进先出 + 维护最大（小）值

class Mdeque:
    def __init__(self):
        self.que = collections.deque()

    def push(self, val):
        while self.que and val > self.que[-1]: # if val==que[-1], keep both
            self.que.pop()
        self.que.append(val)
    
    def pop(self, val):
        if self.que and self.que[0] == val:
            self.que.popleft()

    def top(self):
        return self.que[0]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        que = Mdeque()
        for i in range(k):
            que.push(nums[i])
        res.append(que.top()) # res.append(que[0]) --- 不work.
        for i in range(k, len(nums)):
            que.pop(nums[i-k])
            que.push(nums[i])
            res.append(que.top())
        return res

• 另一个版本

[1]
[3]
[3,-1]
[3,-1,-3]
[5]
[5,3]
[6]
[7]

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums, k: int):
        queue = deque()
        result = []
        left = 0
        for right in range(len(nums)):
            #  如果队列不为0 ， 或者当前元素 大于队列里面的元素， 就将queue里面的元素剔除。
            while len(queue) > 0 and nums[right] >= nums[queue[len(queue) - 1]]:
                queue.pop()
            queue.append(right)
            # 如果队列里面的队首元素 在left 的左边，说明已经在窗口外了，剔除。
            if queue[0] < left:
                queue.popleft()

            # 如果已经形成了窗口
            if right + 1 >= k:
                result.append(nums[queue[0]])
                left += 1
        return result

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        que = collections.deque()
        res = []
        for i in range(n):
            while que and nums[que[-1]] <= nums[i]:
                que.pop()
            que.append(i) 
            if i - que[0] + 1 > k:
                que.popleft()
            if i >= k-1:
                res.append(nums[que[0]])
        return res  

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums) 
        que = collections.deque() 
        res = []
        for i in range(n):
            num = nums[i] 
            while que and num >= nums[que[-1]]: # !!!
                que.pop() 
            que.append(i)   
            if i - que[0] + 1 > k: # !!!
                que.popleft()  
            if i >= k-1:
                res.append(nums[que[0]])
        return res   

347. 前 K 个高频元素

• 思路
  • example
  • 用字典统计数字频率
  • 把[freq, num]用小顶堆(size=k，以freq为值)维护。
• 复杂度. 时间：, 空间:

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        table = collections.defaultdict(int)
        for num in nums:
            table[num] += 1
        que = []
        for num, freq in table.items():
            heapq.heappush(que, [freq, num])
            if len(que) > k: 
                heapq.heappop(que)
        return [x[1] for x in que]

• 桶排序
• 时间, 空间

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        table = collections.defaultdict(int)
        max_freq = 0
        for num in nums:
            table[num] += 1
            max_freq = max(max_freq, table[num])
        table2 = [[] for _ in range(max_freq+1)]
        for num, freq in table.items():
            table2[freq].append(num)
        res = []
        for i in range(max_freq, 0, -1):
            if table2[i]:
                for num in table2[i]:
                    res.append(num)
                    if len(res) == k:
                        return res

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        table1 = collections.defaultdict(int)
        max_freq = 0
        for num in nums:
            table1[num] += 1
            max_freq = max(max_freq, table1[num])
        table2 = collections.defaultdict(list)
        for key, val in table1.items():
            table2[val].append(key) 
        cnt = 0
        res = []
        for i in range(max_freq, -1, -1):
            if table2[i]:
                for num in table2[i]:
                    res.append(num)
                    cnt += 1
                    if cnt == k:
                        return res 

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]: 
        table = collections.defaultdict(int)  
        max_freq = 0
        for num in nums:
            table[num] += 1
            max_freq = max(max_freq, table[num])
        table2 = collections.defaultdict(list)  
        for num, freq in table.items():
            table2[freq].append(num)
        cnt = 0
        res = []
        for freq in range(max_freq, -1, -1):
            if len(table2[freq]) > 0:
                while table2[freq]:
                    res.append(table2[freq].pop()) 
                    cnt += 1
                    if cnt == k:
                        return res  

215. 数组中的第K个最大元素

• 思路
  • example
  • 维护大小为K的小顶堆
• 复杂度. 时间：, 空间:

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        que = []
        for i in range(k):
            heapq.heappush(que, nums[i])
        for i in range(k, len(nums)):
            if nums[i] > que[0]:
                heapq.heappop(que)
                heapq.heappush(que, nums[i])
        return que[0]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        que = []
        for num in nums:
            heapq.heappush(que, num)
            if len(que) > k:
                heapq.heappop(que)
        return que[0]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        que = []
        for i in range(k):
            heapq.heappush(que, nums[i])
        for i in range(k, n):
            if nums[i] > que[0]:
                heapq.heappop(que) 
                heapq.heappush(que, nums[i])
        return que[0] 

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums) 
        que = [] 
        for i in range(k):
            heapq.heappush(que, nums[i]) 
        for i in range(k, n):
            if nums[i] > que[0]:
                heapq.heappop(que) 
                heapq.heappush(que, nums[i]) 
        return que[0]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums) 
        que = []
        for num in nums:
            if len(que) < k or num > que[0]:
                heapq.heappush(que, num)
            if len(que) > k:
                heapq.heappop(que) 
        return que[0] 

• 其它方法

TBA

4. 寻找两个正序数组的中位数

• 第k小 (k >= 1), 二分查找

m+n 奇数：k = (m+n)//2 + 1
m+n 偶数：k = (m+n)//2, (m+n)//2+1 --> average
nums1[index1,...,index1+k//2-2], nums2[index2,...,index2+k//2-2] 假设没有越界情况
pivot1 = nums1[index1+k//2-1], pivot2 = nums2[index2+k//2-1]
Case 1: pivot1 <= pivot2, pivot1 不可能是第k小 （最多第k-1小），index1 = min(index1 + k//2, m-1) , 更新k继续搜索直到k=1
Case 2: pivot1 > pivot2, pivot2 不可能是第k小 （最多第k-1小），index2 = min(index2 + k//2, n-1)， 更新k继续搜索直到k=1

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def getKth(nums1, nums2, k):
            index1, index2 = 0, 0 
            while True:
                if index1 == m:
                    return nums2[index2+k-1]
                if index2 == n:
                    return nums1[index1+k-1]
                if k == 1: # 放在这里 
                    return min(nums1[index1], nums2[index2])
                newIndex1 = min(index1+k//2-1, m-1)
                newIndex2 = min(index2+k//2-1, n-1)
                pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
                if pivot1 <= pivot2:
                    k -= newIndex1 - index1 + 1 # 这个先 
                    index1 = newIndex1 + 1
                else:
                    k -= newIndex2 - index2 + 1
                    index2 = newIndex2 + 1
            # k = 1
            # return min(nums1[index1], nums2[index2]) #  有可能idex1 or index2越界
        m, n = len(nums1), len(nums2) 
        if (m+n) % 2 == 1:
            return getKth(nums1, nums2, (m+n)//2+1)
        else:
            return (getKth(nums1, nums2, (m+n)//2) + getKth(nums1,nums2, (m+n)//2+1)) / 2

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def getKth(k):
            left1, left2 = 0, 0 # !!!
            while k >= 1: 
                if left1 == m: # !!!
                    return nums2[left2+k-1]
                if left2 == n: # !!!
                    return nums1[left1+k-1] 
                if k == 1: # !!!
                    return min(nums1[left1], nums2[left2])
                right1 = min(left1+k//2-1, m-1) # valid index in nums1
                right2 = min(left2+k//2-1, n-1) # valid index in nums2
                pivot1, pivot2 = nums1[right1], nums2[right2]  
                if pivot1 <= pivot2:
                    k -= right1 - left1 + 1
                    left1 = right1 + 1
                else:
                    k -= right2 - left2 + 1
                    left2 = right2 + 1
        m, n = len(nums1), len(nums2)  
        if (m+n) % 2 == 1:
            return getKth((m+n)//2+1) 
        else:
            return (getKth((m+n)//2) + getKth((m+n)//2+1)) / 2

• 进阶，多个正序数组？