经典算法 —滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[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

• 看到这个问题第一眼的想法是先遍历截取k为一个数据，找到最大的值

  /**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    var result = []
    for(var i = 0; i < nums-k; i++) {
        var maxNum = nums[i]
        for( var j = i + 1 ; j < i + k ; j++) {
          if(nums[j] - nums[i]) {
              maxNum  =  nums[j]
          }
        }
        result.push(maxNum )
    }
    return result
};

• 换个思路就是一个队列问题，一次性放入数据，最前面的永远是最大的，最后一个，比前面的大的话，前面的数据都可以清除

  /**
 * @author lastbee@163.com
 * @param {number []} nums
 * @param {number} k
 * @return {number []}
 */
var slidingWindow = function(nums, k) {
  if (nums.length == 0) return []
  let window = []//队列用来存放下标
  let result= []
  for((val i= 0；i < nums.length-1 ; i ++) {  
    if( i >= k && window[0] <= index- k )  {
      window.shift()//队列头抛出
    }
    for(var j = window.length-1; j>= 0; j--) {
      if(nums[window[window.length - 1]] <= nums[i]) {
          window.pop()
        } else {
          break;
        }
      }
    v window.push(index)
      if (index >= k - 1) {
        result.push(nums[window[0]])
      }
  }
  return result
}

• 优化之后

/**
 * @author lastbee@163.com
 * @param {number []} nums
 * @param {number} k
 * @return {number []}
 */
  var slidingWindow = function(nums, k) {
    if (nums.length == 0) return []
    let window = []//队列用来存放下标
    let res = []
    nums.forEach((item, index) => {
      if (index >= k && window[0] <= index - k) {
          window.shift()//队列头抛出
      }
      while (window && nums[window[window.length - 1]] <= item) {
          window.pop()//队列为抛出
      }
      window.push(index)
      if (index >= k - 1) {
          res.push(nums[window[0]])
      }
    })
   return res
 }