leetcode 703:データストリームのK番目の大きな要素を見つけるクラス(class)を設計する.注意は、ソート後のK番目の大きな要素であり、K番目の異なる要素ではありません.

:データストリームのK番目の大きな要素を見つけるクラス(class)を設計します.注意は、ソート後のK番目の大きな要素であり、K番目の異なる要素ではありません.
KthLargestクラスには、データストリームの初期要素を含む整数kと整数配列numsを同時に受信するコンストラクタが必要です.KthLargestを呼び出すたびにaddは、現在のデータストリームのK番目に大きい要素を返します.
例:
int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3);//returns 4 kthLargest.add(5);//returns 5 kthLargest.add(10);//returns 5 kthLargest.add(9);//returns 8 kthLargest.add(4);//returns 8
説明:numsの長さ≧k−1およびk≧1を仮定できます.Related Topicsスタック1390
解答:方法1:直接ソート法

class KthLargest(object):

    def __init__(self, k, nums):
        """
        :type k: int
        :type nums: List[int]
        """
        self.nums = nums
        self.k = k
        self.nums.sort(reverse = True)
        while len(self.nums) > k:
            self.nums.pop()
        
    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        self.nums.append(val)
        self.nums.sort(reverse = True)
        if len(self.nums) > self.k:
            self.nums.pop()
        return self.nums[-1]

方法2:最小スタックheapq注意:pythonスタックheapqスタックを使用して説明する

import heapq
# leetcode submit region begin(Prohibit modification and deletion)
class KthLargest(object):
    def __init__(self, k, nums):
        """
        :type k: int
        :type nums: List[int]
        """
        self.pool = nums
        heapq.heapify(self.pool)
        self.k = k
        while len(self.pool) > k:
            heapq.heappop(self.pool)
    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        if len(self.pool) < self.k:
            heapq.heappush(self.pool, val)
        elif val > self.pool[0]:
            heapq.heapreplace(self.pool, val)
        return self.pool[0]        

まとめは,スタックの構造的特徴とpythonが提供するいくつかのスタックの関数機能を理解する必要がある.
簡単な式でスタックの定義を説明します.
大頂炉:arr[i]>=arr[2 i+1]&&arr[i]>=arr[2 i+2]
小天井スタック:arr[i]<=arr[2 i+1]&&arr[i]<=arr[2 i+2]