Heap: Maximum Element in a Stream

👩‍💻 문제

Write a function named stream_max that takes as its input a list of integers (nums). The function should return a list of the same length, where each element in the output list is the maximum number seen so far in the input list.

More specifically, for each index i in the input list, the element at the same index in the output list should be the maximum value among the elements at indices 0 through i in the input list.

Use the provided MaxHeap class to solve this problem. You should not need to modify the MaxHeap class to complete this task.

Function Signature: def stream_max(nums):

 

 

Examples:

If the input list is [1, 3, 2, 5, 4], the function should return [1, 3, 3, 5, 5].

Explanation:

• At index 0, the maximum number seen so far is 1.
• At index 1, the maximum number seen so far is 3.
• At index 2, the maximum number seen so far is still 3.
• At index 3, the maximum number seen so far is 5.
• At index 4, the maximum number seen so far is still 5.

So, the output list is [1, 3, 3, 5, 5].

 

이제까지중에 가장 큰 애를 리스트에 담는거다! 

 

💡 직관적 풀이

def stream_max(nums):
    stream = MaxHeap()
    res = []
    for i in nums:
        stream.insert(i)
        if i <= stream.heap[0]:
            res.append(stream.heap[0])
        else:
            res.append(i)
    return res

 

내가 푼건데... 그냥 의식의 흐름대로

어쨌든 '이제까지중'에 제일 큰 애가 리스트에 추가돼야 하니까,

지금까지의 max가 더 크면 그걸 넣고, 아니면 지금의 값을 넣는다... 하는 흐름이고 틀린 건 아닌데

 

💡 훨씬 더 맞는 풀이...!

def stream_max(nums):
    max_heap = MaxHeap()
    max_stream = []
    for num in nums:
        max_heap.insert(num)
        max_stream.append(max_heap.heap[0])
    return max_stream

 

결국, '이제까지의 최대값' 을 그냥 append하면 되니까,

heap에 계속 추가해주고, 추가될때마다 그 최대값을 리스트에 append하면 되는 아주 간단한 문제잖아

 

 

✍️ 해설

쉬운데 쉽게 쉽게 풉시다

 

 

🥳 배운점