239. Sliding Window Maximum

sliding-window-maximum.go

// https://leetcode.com/problems/sliding-window-maximum
// 
// Time: O(n)
// Space: O(n)
//
// n = number of elements in array

// .................... //

func maxSlidingWindow(nums []int, k int) []int {
    n := len(nums)

    res := make([]int, 0)
    deque := make([]int, 0)

    l, r := 0, 0
    for r < n {
        for len(deque) > 0 && nums[r] > nums[deque[len(deque)-1]] {
            deque = deque[:len(deque)-1]
        }
        deque = append(deque, r)

        if (r-l+1) == k {
            res = append(res, nums[deque[0]])
            if nums[deque[0]] == nums[l] {
                deque = deque[1:]
            }
            l++
        }

        r++
    }

    return res
}