239. Sliding Window Maximum.md

239. Sliding Window Maximum.md

Problem

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.

For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

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
Therefore, return the max sliding window as [3,3,5,5,6,7].

tag:

Solution

Solution : use deque O(n)

核心思想是窗口移动过程中，删除前一个窗口中不需要考虑的元素，维护一个双端队列，队列内为当前窗口内降序排列的元素（比如window=[1,2,7,4],则deque=[7,4]），队列左端存储当前窗口最大元素：

当一个新值nums[i]到来时，其窗口范围为[i-k+1, i]，维护过程如下：

• 保证队列内的元素为当前窗口元素，即删除下标j<i-k+1的元素
• 保证队列内的元素降序排列，删除队列内num[x]<num[i]的元素，因为num[x]不可能是当前窗口或后继窗口的最大元素，不需要考虑
• 把num[i]加入队列，则队头为当前窗口的最大元素

举例：

1,2,7,3,8,5,3,2
-----window------   ------deque----  ----details----
|1,2,7|,3,8,5,3,2   7                元素1，2在后继窗口中不需要考虑
1,|2,7,3|,8,5,3,2   7,3              由于元素3有可能是后继窗口的最大值，需要考虑
1,2,|7,3,8|,5,3,2   8
1,2,7,|3,8,5|,3,2   8，5
1,2,7,3,|8,5,3|,2   8，5，3
1,2,7,3,8,|5,3,2|   5，3，2           由于元素8不再当前窗口内，从队列删除

java

	public int[] maxSlidingWindow(int[] nums, int k) {
	    if(nums.length==0) {
	        return new int[0];
	    }
		Deque<Integer> q = new ArrayDeque<Integer>();
		int[] res = new int[nums.length-k+1];
		int j=0;
		for(int i=0; i<nums.length; i++) {
			while(!q.isEmpty() && q.peekFirst()<i-k+1) q.pollFirst();
			while(!q.isEmpty() && nums[q.peekLast()]<nums[i]) q.pollLast();
			q.offerLast(i);
			if(i>=k-1) {
				res[j++] = nums[q.peekFirst()];
			}
		}
		return res;
	}

go

func maxSlidingWindow(nums []int, k int) []int {
	n, r := len(nums), make([]int, 0, len(nums)-k+1)
	if n == 0 {
		return r
	}
	l := list.New()

	for i := 0; i < n; i++ {
		for l.Len() != 0 && l.Front().Value.(int) < i-k+1 {
			l.Remove(l.Front())
		}
		for l.Len() != 0 && nums[l.Back().Value.(int)] < nums[i] {
			l.Remove(l.Back())
		}
		l.PushBack(i)
		if i >= k-1 {
			r = append(r, nums[l.Front().Value.(int)])
		}
	}
	return r
}