[Leetcode] 239. Sliding Window Maximum_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '239. Sliding Window Maximum'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Sliding Window Maximum' 알고리즘 문제

 

STEP 2. 'Sliding Window Maximum' 코드(code)

 

STEP 3. 'Sliding Window Maximum' 해설

 

STEP 4. 'Sliding Window Maximum' solution

 

반응형

 

STEP 1. 'Sliding Window Maximum' 알고리즘 문제

 

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

 

정수 num의 배열이 주어지면 배열의 맨 왼쪽에서 맨 오른쪽으로 이동하는 k 크기의 슬라이딩 윈도우가 있습니다. 윈도우는 k개 숫자만 볼 수 있습니다. 슬라이딩 창이 한 위치씩 오른쪽으로 이동할 때마다, 최대 슬라이딩 윈도우를 반환합니다.

 

Constraints:

 

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

 

---

STEP 2. 'Sliding Window Maximum' 코드(code)

 

■ Runtime: Time Limit Exceeded
■ Memory: Time Limit Exceeded

 

Max heap을 적용해서 문제를 접근했지만, 해당 방법은 Out of memory 문제가 발생하였습니다.

---

STEP 3. 'Sliding Window Maximum' 해설

 

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        '''Make array in to max Heap'''
        def max_heapify(arr):
            # Get the last array index
            last = len(arr)//2 -1

            for current in range(last, -1, -1):

                # Loop until at the end of array
                while current <= last:
                    # Heap is binary tree structure
                    child = current *2 +1
                    sibling = child +1

                    # If child is smaller than sibling, then swith each others.
                    if sibling < len(arr) and arr[child] < arr[sibling]:
                        child = sibling 

                    # If current values is smaller than child (=sibling), then switch each others.
                    if arr[current] < arr[child]:
                        arr[current], arr[child] = arr[child], arr[current]
                        current = child
                    else:
                        break

        '''ADD NEW ELEMENT IN TO MAX HEAP'''
        def max_heappush(arr, data):
            arr.append(data)

            current = len(arr) - 1

            while current > 0:
                parent = (current -1) // 2

                # If appended value is bigger than parent, then switch with parent node.
                if arr[parent] < arr[current]:
                    arr[parent], arr[current] = arr[current], arr[parent]

                    current = parent
                else:
                    break

        answer_lst = []

        for idx in range(len(nums)-k+1):
            # First step, make temp array
            if idx == 0 :
                temp_nums = sorted(nums[idx:idx+k], reverse =True)
            # From second step, heap push the new element
            else:
                max_heapify(temp_nums)
                max_heappush(temp_nums, nums[idx+k-1])
            
            answer_lst.append(temp_nums[0])
            temp_nums.remove(nums[idx])

        return answer_lst

 

 

STEP 4. 'Sliding Window Maximum' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 143ms Beats 88.61%
■ Memory: 30.70 MB Beats 58.88%

 

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        q = deque()

        for idx, num in enumerate(nums):
            # Maintain the deque in descending order
            while q and q[-1] < num:
                q.pop()
            q.append(num)

            # Remove the elements which are out of this window
            if idx >= k and nums[idx-k] == q[0]:
                q.popleft()
            
            # Append the maximum of the current window to the result
            if idx >= k-1:
                res.append(q[0])

        return res

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '239. Sliding Window Maximum'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.