LeetCode 239. 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.

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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note: 
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow up:
Could you solve it in linear time?

Hint:

1. 1. How about using a data structure such as deque (double-ended queue)?
   2. The queue size need not be the same as the window’s size.
   3. Remove redundant elements and the queue should store only elements that need to be considered.

题解：

用deque, 里面存index.

从尾部添加index前先检查deque的尾部index对应的元素nums[deque.getLast()]是否比要添加的元素nums[i]小或者相等，若是，就把尾部index remove掉，一直remove直到遇到比nums[i]大的数或者LinkedList 为空。e.g. 当添加nums[1] = 3的index 1时，最大的数肯定是3，1就没有用了。也就是说如果出现比先添加的数大的数时，先添加的就没有用了。

如此deque里面保存的就是[第一大index, 第二大index, 第三大index, 第四大index...].

若是i - 头部的index >= k, 就说明现在的window大小已经大于了k, 就需要从头remove一次.

当 i+1>=k 是开始记录res. res的坐标为i-k+1, 取ls的头index, 也就是当前窗口的最大index. 把对应的元素加大res中。

Time Complexity: O(n). 每个元素最多进deque一次, 出deque一次. Space O(k).

AC Java:

 1 public class Solution {
 2     public int[] maxSlidingWindow(int[] nums, int k) {
 3         if(k == 0){
 4             return new int[0];
 5         }
 6         
 7         int [] res = new int[nums.length-k+1];
 8         LinkedList deque = new LinkedList();
 9         for(int i = 0; i){
10             while(!deque.isEmpty() && nums[deque.getLast()]<=nums[i]){
11                 deque.removeLast();
12             }
13             deque.addLast(i);
14             if(i - deque.getFirst() >= k){
15                 deque.removeFirst();
16             }
17             if(i+1>=k){
18                 res[i+1-k] = nums[deque.getFirst()];
19             }
20         }
21         return res;
22     }
23 }

转载于:https://www.cnblogs.com/Dylan-Java-NYC/p/4938106.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！