---
# System prepended metadata

title: '**Leetcode筆記(Kth Largest Element in a Stream)**'
tags: [heap, easy, design, leetcode]

---

# **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)。
```python
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]一定是最小的特性，去回傳最大裡面的最小
```python
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)
```

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

```python

```
---


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

:::


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

:::

**思路**


**講解連結**

Provided by. 

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