I've searched this site and find many similar questions, but not exactly the same as the one I'll post.
This attempts to solve Leetcode 239:
You are given an array of integers
nums
, there is a sliding window of sizek
which is moving from the very left of the array to the very right. You can only see thek
numbers in the window. Each time the sliding window moves right by one position.Return the max sliding window.
The subject is - given an integer array, and positive integer k, denoting the sliding window size. Each time you can only slide from left to right one position, try to find each windows maximum number and output these maximum number into an output list. [Note - the given list could be very large ~ 1 Million (nums)]
For example: Given a nums array = [99, 74, 48, 27, 56, 88, 66, 77, 101]; k = 3 Output should be: [99, 74, 56, 88, 88, 88, 101]
I've tried to solve this in Python, and wonder if it could be further optimized and improved.
def maxSliding(nums: List[int], k: int) -> List[int]:
if not k or not nums: return []
z = len(nums)
if z <= k: return [max(nums, default = 0)]
q = deque([])
res = []
for i, num in enumerate(nums):
if q and q[0] == i-k:
q.popleft()
while q and nums[q[-1]] < num:
q.pop()
q.append(i)
if i >= k-1: res.append(nums[q[0]])
return res
# Since every num. enters and leaves the queue at most once, the time
# complexity is O(len(A)), independent of the value of K.
if __name__ == '__main__':
B = [99, 74, 48, 27, 56, 88, 66, 77, 101]
print(maxSliding(B, 3))