leetcode hard : Sliding Window Maximum

https://leetcode.com/problems/sliding-window-maximum/

Sliding Window Maximum - LeetCode

 

얼핏 봐선 그냥 sliding window를 heap에 넣으면 될거같이 생겼지만
생각해보니 heap은 원하는 요소를 빼는 연산이 없구나.

억지로 빼고 heapify를 다시 하는 방법도 있긴 하지만 썩 깔끔해보이진 않는다.

그리고 N log N보단 N으로 푸는ㄱ ㅔ맞는거같아보임.

 

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums : return []

        n = len(nums)
        answer = []
        mstack = deque()

        for i in range(n):
            if mstack and mstack[0] <= i - k : mstack.popleft()
            while mstack and nums[mstack[-1]] <= nums[i]: mstack.pop()
            mstack.append(i)
            if i - k + 1 >= 0: answer.append(nums[mstack[0]])

        return answer

 

핵심은 decreasing 형태의 monotonick stack을 sliding window적용시키면서 유지해가는것이다.

그럼 그 사이에 monotonick stack 유지하면서 pop되는 멤버들은 어떡하냐? 걔네는 sliding window 내에서 절대 max값이 될 일이 없다. 양옆으로 자기보다 더 큰애들이 껴있기 때문에..

그럼 그 monotonic stack 제일 바닥에 있는애가 max값이 된다.

 

O(N)