# **Leetcode筆記(Kth Largest Element in a Stream)**

:::info
:information_source: 題目 : Kth Largest Element in a Stream, 類型 : heap , 等級 : easy
日期 : 2023/07/08，2024/10/17
:::

### 嘗試
**如果要把init的變數拿來用的話，要添加成self，變成全域變數**

- 時間複雜度：
- 在 `__init__` 方法中，首先將 `nums` 列表賦值給 `self.minHeap`，時間複雜度為 O(N)，其中 N 是 `nums` 列表的長度。
- 時間複雜度為 O((N - k) log k)，因為每次彈出操作的時間複雜度是 O(log k)，需要執行的次數最多為N - k 。
- `heapq.heappush` 和`heapq.heapop`的時間複雜度是 O(log k)。

- 空間複雜度：
- 使用了一個大小為 N 的列表 `self.minHeap` 來存儲初始的元素，空間複雜度為 O(N)。
- 在 `add` 方法中，沒有引入額外的資料結構，空間複雜度是 O(1)。

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.minHeap, self.k = nums, k # minHeap會傾向留下最大的
        heapq.heapify(self.minHeap)
        while len(self.minHeap) > k:
            heapq.heappop(self.minHeap)
        
    def add(self, val: int) -> int:
        # 並不需要pop數字出來
        heapq.heappush(self.minHeap, val)
        if len(self.minHeap) > self.k:
            heapq.heappop(self.minHeap)
        return self.minHeap[0]

2024/10/17
把所有數字都存進去會超時，minheap傾向存大，那就固定留下k個最大的，並且用minheap[0]一定是最小的特性，去回傳最大裡面的最小

class KthLargest:
    def __init__(self, k: int, nums: list):
        self.nums = nums
        self.k = k
        heapq.heapify(self.nums)
        while len(self.nums) > self.k:
            heapq.heappop(self.nums)
    
    def add(self, val: int):
        heapq.heappush(self.nums, val)
        while len(self.nums) > self.k:
            heapq.heappop(self.nums)
        return self.nums[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

---
### **優化**

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**

**講解連結**

Provided by.

###### tags: `heap` `easy` `leetcode`