LeetCode [703]: Kth Largest Element in a Stream

📌 LeetCode [703]: Kth Largest Element in a Stream

🔗 문제 링크

---

문제 설명 📄

k번째로 큰 요소를 효율적으로 추적할 수 있는 클래스 KthLargest를 구현해야 합니다.

• KthLargest는 두 가지 주요 작업을 처리합니다:
  1. 초기화: 주어진 nums 리스트와 k값을 기반으로 초기화.
  2. 값 추가: 새로운 값을 추가하고 현재 k번째로 큰 값을 반환.

---

Solution 💻

import heapq
class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.q = []
        for num in nums:
            heapq.heappush(self.q, num)
            if len(self.q) > k: 
                heapq.heappop(self.q)

    def add(self, val: int) -> int:
        heapq.heappush(self.q, val)
        if len(self.q) > self.k:
            heapq.heappop(self.q)
        return self.q[0]

시간 복잡도 분석 ⏲️

• 초기화:
  • 리스트의 모든 요소를 힙에 추가하면서 크기를 유지. O(n log k)
  • n은 nums의 길이, k는 힙 크기.
• add 메서드:
  • O(log k): 힙에 요소를 추가하거나 제거.

---

공간 복잡도 분석 🗄️

• 힙 크기: 항상 k로 제한됨. O(k).

---