[python]デュアル・ユーティリティ・プリアンブル・キュー




1 Try

import heapq
def solution(operations):
    answer = [0,0]
    stack = []

    for o in operations:
        try:
            line = o.split(' ')
            operator, num = line[0], int(line[1])
            if operator == 'I': # 해당 값 삽입
                stack.append(int(num))
            elif int(num) == -1: # 최솟값 삭제
                stack.remove(min(stack))
            else : # 최댓값 삭제
                stack.remove(max(stack))
            if(len(stack) == 0):
                answer = [0,0]
            else :
                answer = [max(stack), min(stack)]
        except :
            continue

    return answer
  • why? Array insert時int->string
  • ホットスポットが最適化されていないため
  • を通過する.
  • ホットスポットの最適化->heapqには
  • が必要になる場合があります.

    others

    from heapq import heappush, heappop
    
    def solution(arguments):
        max_heap = []
        min_heap = []
        for arg in arguments:
            if arg == "D 1":
                if max_heap != []:
                    heappop(max_heap)
                    if max_heap == [] or -max_heap[0] < min_heap[0]:
                        min_heap = []
                        max_heap = []
            elif arg == "D -1":
                if min_heap != []:
                    heappop(min_heap)
                    if min_heap == [] or -max_heap[0] < min_heap[0]:
                        max_heap = []
                        min_heap = []
            else:
                num = int(arg[2:])
                heappush(max_heap, -num)
                heappush(min_heap, num)
        if min_heap == []:
            return [0, 0]
        return [-heappop(max_heap), heappop(min_heap)]
    min
  • heapq;最大heapqueを実施すると
  • である