剑指 Offer 59 - I. 滑动窗口的最大值

题目链接： 剑指 Offer 59 - I. 滑动窗口的最大值

题目描述：

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

解法思路：
单调队列：

• 维护一个单调的队列，队列中保存的是对应数字的数组下标
• 每新加进来一个元素，首先删除队头（超出滑动窗口的范围的值）
• 然后比较当前元素与队尾元素，删除哪些比当前元素小的队尾元素
• 最后，将当前的队头元素加到res中

代码：

func maxSlidingWindow(nums []int, k int) []int {
    var res []int
    n := len(nums)
    if n == 0 {
      return res
    }
    var q []int  //单调队列(里面存的是下标)
    for i:=0; i < n ;i++{
      //去除对头多余的元素
      for len(q) > 0 && i-k >= q[0] {
          q = q[1:]
      }
      // 去除队尾比当前值小的元素(这里等于也要删掉)
      for len(q) > 0 && nums[q[len(q)-1]] <= nums[i]{
         q = q[:len(q)-1]
      } 
      // 将当前元素的下标加入到队列q中
      q = append(q,i)
      // 队头元素就是窗口的最大值
      if i >= k - 1 {
        res = append(res,nums[q[0]])
      }
    }
    return res
}