[python]Hip双優先級キュー[3ステップ]

8877 ワード

問題の説明


デュアル・ユーティリティ・プリアンブル・キューとは、次の演算が可能なデータ構造です.
コマンド受信タワー(高さ)Iのデジタルキューに指定した数字を挿入します.D 1キューから最値を削除します.D-1キューから最大値を削除します.
パラメータとして2つの優先順位キューで実行する演算操作を指定した場合、すべての演算を処理した後、キューが空の場合[0,0]空でない場合、「最値、最上昇値」を返すソルバを実装します.

せいげんじょうけん


operationsは、長さが1または1000000未満の文字列配列です.
operationsの要素は、キューが実行する演算を表します.
要素はコマンドデータ形式で与えられます.最大値/最大値を削除する操作で複数の最大値/最大値がある場合は、1つだけ削除します.
空のキューからデータを削除する必要がある場合は、この操作は無視されます.

I/O例


operationsreturn["I 16","D 1"][0,0]["I 7","I 5","I -5","D -1"][7,5]

I/O例説明


16を挿入すると、最大値が削除されます.[0,0]を返します.空ですから.
7、5、および-5を挿入して、最大値を削除します.最大値7、最小値5を返します.

Java解釈

import heapq

def solution(operations):
    answer = []
    heap = []   # 힙 생성

    for data in operations:
        # 연산이 "I"일 경우 공백 뒤의 숫자를 heap에 넣음
        if data[0] == "I":
            heapq.heappush(heap, int(data[2:]))
        # 연산이 "D"일 경우
        else:
            if len(heap) == 0:
                pass
            # 공백 뒤가 "-"일 경우 최소힙을 제거
            elif data[2] == "-":
                heapq.heappop(heap)
            # 공백 뒤가 아무것도 아닌 경우
            else:
                # 힙에서 가장 큰 수를 제외하고 다시 힙에 넣음
                heap = heapq.nlargest(len(heap), heap)[1:]
                heapq.heapify(heap)

    if heap:
        answer.append(max(heap))
        answer.append(min(heap))
    else:
        answer.append(0)
        answer.append(0)
    
    return answer
import heapq

def solution(operations):
    min_heap = []
    for value in operations:
        order, data = value.split()
        data = int(data)
        # 최댓값 삭제
        if order == "D" and data == 1:
            if min_heap:
                max_value = max(min_heap)
                min_heap.remove(max_value)
        # 최솟값 삭제
        elif order == "D" and data == -1:
            if min_heap:
                heapq.heappop(min_heap)
        # 큐 데이터 삽입
        else:
            heapq.heappush(min_heap, data)
    
    # heap이 비어있는 경우
    if not min_heap:
        return [0, 0]
    return max(min_heap), min_heap[0]