Leetcode # 239. ⭐️ Sliding Window Maximum

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

First Solution

Time Complexity: O((n – k) * log(k))
Space Complexity: O(k)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    def find_i(nums, num, left=0, right=-1): 
      right += (len(nums) + 1) if right < 0 else 1
      while left < right:
        mid = (left + right) // 2
        if nums[mid] < num: left = mid + 1 
        else: right = mid
      return left

    ans = []
    left = 0
    curr = []
    for right in range(len(nums)):
      # do logic here to add arr[right] to curr
      curr.insert(find_i(curr, nums[right]), nums[right])
      while right - left + 1 > k:
        # remove arr[left] from curr
        curr.pop(find_i(curr, nums[left]))
        left += 1
      # update ans
      if right - left + 1 == k: ans.append(curr[-1])
    
    return ans

Better Solution

curr :=
[i for i in range(left, right + 1)
   if all(nums[i] > nums[j] for j in range(i + 1, right + 1))]
⇒ curr_nums := [nums[i] for i in curr] is strictly decreasing
≡ curr[0] 總是等於 max(curr_nums)
且只有在離開 sliding window 時會被移除

Time Complexity: O(n)
Space Complexity: O(k)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    ans = []
    left = 0
    curr = deque()
    for right in range(len(nums)):
      # do logic here to add arr[right] to curr
      while curr and nums[right] >= nums[curr[-1]]:
        curr.pop()
      curr.append(right)
      while right - left + 1 > k:
        # remove arr[left] from curr
        if curr[0] == left:
          curr.popleft()
        left += 1
      # update ans
      if right - left + 1 == k: ans.append(nums[curr[0]])
    
    return ans

Last Updated on 2023/08/16 by A1go