Changchun Master Li

leetcode 239. Sliding Window Maximum

2016-12-01

Python暴力通关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        ret = []
        length = len(nums)
        if 0 == length:
            return []
        w = length - k + 1
        for i in range(w):
            m = max(nums[i:i+k])
            ret.append(m)
        return ret

JavaScript双向队列 时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var maxSlidingWindow = function(nums, k) {
  //构造一个双向队列
  var window = [];

  var answer = [];
  for(var i = 0; i < nums.length; i++) {

    //删除窗口外的索引
    if(0 != window.length && window[0] == i - k)
      window.shift();

    //每一次新加入的索引时，窗口中值比这个索引小的索引
    //在接下来的窗口移动中永远不会在起作用
    //也就是说，窗口内索引值是有序的

    //依次删除窗口内无效的索引
    while(0 != window.length && nums[window[window.length - 1]] < nums[i])
      window.pop();

    window.push(i);
    if(i >= k-1)
      answer.push(nums[window[0]]);
  }
  return answer;
};
Tags: algorithm leetcode
← leetcode 126. Word Ladder II 有序对的js实现 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章