This program demonstrates how to find the maximum value in each sliding window of size k in an array using the Go programming language. The key technique employed is the use of a deque to maintain the indices of useful elements of the current window of size k. These indices are maintained in such a way that the array values at these indices are in a decreasing order. Thus, the front of the deque always holds the index of the maximum value for the current window.

Program Code

package main

import (
    "fmt"
)

// maxSlidingWindow returns the maximum values in each sliding window of size k.
func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 || k <= 0 { return nil } var result []int var deque []int // holds indices for i, num := range nums { // Remove indices that are out of this window if len(deque) > 0 && deque[0] < i-k+1 { deque = deque[1:] } // Remove from deque all elements less than the currently being added element for len(deque) > 0 && nums[deque[len(deque)-1]] < num { deque = deque[:len(deque)-1] } // Add current element at the end of deque deque = append(deque, i) // Window has reached its size k, so append the current maximum to the result if i >= k-1 {
            result = append(result, nums[deque[0]])
        }
    }

    return result
}

func main() {
    nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
    k := 3
    fmt.Println("Array:", nums)
    fmt.Println("Sliding window size:", k)
    fmt.Println("Maximums of each sliding window:", maxSlidingWindow(nums, k))
}

Explanation

• The function maxSlidingWindow takes an array and the size of the sliding window k as input.
• It uses a slice deque to keep track of the indices of the array elements. These indices are always arranged in a way that their corresponding values are in decreasing order.
• For each element in the array, the function checks if the first element in the deque is out of the current window’s range (line 14). If it is, it is removed.
• If any elements in the deque are smaller than the current element, they are removed from the deque (lines 18-20). This maintains the order.
• After processing each element, if the current index is at least k-1, the value corresponding to the index at the front of the deque is added to the result list. This is because the deque always contains the index of the largest element for the current sliding window.

How to Run the Program

To run the program, you need to have Go installed on your computer:

1. Save the above code to a file with a .go extension, for example, slidingwindow.go.
2. Open a terminal or command prompt.
3. Navigate to the directory containing the file.
4. Run the program by typing go run slidingwindow.go.

This program will output the maximums of each sliding window given the array and window size defined in the main function. Adjust the array and k value in the main function to test different inputs.