Leetcode - Sliding Window Maximum

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

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Follow up:
Could you solve it in linear time?

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 {
        return nums
    }
    leftMax := make([]int, len(nums))
    leftMax[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        if i % k == 0 {
            leftMax[i] = nums[i]
        } else {
            leftMax[i] = getMax(leftMax[i-1], nums[i])
        }
    }
    rightMax := make([]int, len(nums))
    rightMax[len(rightMax)-1] = nums[len(nums)-1]
    for i := len(nums)-2; i >= 0; i-- {
        if i % k == 0 {
            rightMax[i] = nums[i]
        } else {
            rightMax[i] = getMax(rightMax[i+1], nums[i])
        }
    }
    result := make([]int, len(nums)-k+1)
    for i, j := 0, 0; i + k <= len(nums); i++ {
        result[j] = getMax(rightMax[i], leftMax[i + k - 1])
        j++
    }
    return result
}

func getMax(a, b int) int {
    if a > b {
        return a
    }
    return b
}

• 相关文章
• 全局相关文章