算法-数据结构-堆

算法

堆（二叉堆，斐波那契堆）

流式数据第k大（或者第k小）的元素是多少 ;时间负责度nlog2(k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 第k个最大用小顶堆，第k个最小用大顶堆
class KthLargest {
    private int k;
    private PriorityQueue<Integer> q;

    public KthLargest(int k,int[] nums){
        this.k=k;
        this.q=new PriorityQueue<>(k);
        for(int a:nums){
            add(a);
        }
    }

    public Integer add(int val){
        if(q.size()<this.k)
            q.offer(val);
        else if(q.peek()<val){
            q.poll();
            q.offer(val);
        }
        return q.peek();
    }
}

滑动窗口题,每次求最大值

1
2
3
4
5
6
7
8
9
10
11
12
def maxSlidingWindow(nums, k: int):
    if not nums:return []
    window,res=[],[]
    for i,a in enumerate(nums):
        if i>=k and window[0]<=i-k:
            window.pop(0)
        while window and nums[window[-1]]<=a:
            window.pop(-1)
        window.append(i)
        if i>=k-1:
            res.append(nums[window[0]])
    return res