99클럽 코테 스터디 10일차 TIL - 힙

문제

Kth Largest Element in a Stream

풀이

• int가 계속 추가되지만 매번 3번째로 큰 수를 반환해야 한다.
• min heap으로 풀이 가능

코드

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;

class KthLargest {
    private PriorityQueue<Integer> minHeap;
    private int k;
    
    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.minHeap = new PriorityQueue<>();
        
        for(int n : nums){
          this.add(n);
        }      
    }
    
    public int add(int val) {   
        this.minHeap.offer(val);
        
        while(this.minHeap.size() > this.k) this.minHeap.poll();
        
        return this.minHeap.peek();
    }
}

정리

• poll을 하게 되면 최소값을 반환한다.
• k보다 size가 크게 되면 poll을 해서 3번째 최소값을 유지하면 된다.
• 문제 이해하는데 너무 오래 걸림...