- 浏览: 174246 次
- 性别:
- 来自: 济南
文章分类
最新评论
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].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
滑动窗口的题目,我们可以借助双向队列deque来解决。一边维护窗口的大小,一边将每个窗口的中的最大元素放在队列的头部,这样每次取队列的第一个元素就可以了。代码如下:
如果不用队列也可以,思路是一样的,维护一个窗口,当窗口移动之后,检查之前窗口的最大元素是否在移动后的窗口中,如果在只需要比较最大元素与新近的元素就可以;如果不存在就在新窗口中找最大元素。代码如下:
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].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
滑动窗口的题目,我们可以借助双向队列deque来解决。一边维护窗口的大小,一边将每个窗口的中的最大元素放在队列的头部,这样每次取队列的第一个元素就可以了。代码如下:
public class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums == null || nums.length == 0) return new int[0]; int[] result = new int[nums.length - k + 1]; Deque<Integer> deque = new LinkedList<Integer>(); int index = 0; for(int i = 0; i < nums.length; i++) { //查看之前的最大元素是否在窗口中,如果不在就删除 if(!deque.isEmpty() && (deque.getFirst() == (i - k))) deque.removeFirst(); //添加新的元素到队尾 while(!deque.isEmpty() && nums[deque.getLast()] <= nums[i]) deque.removeLast(); deque.addLast(i); //将最大元素加入到结果中 if(i >= k - 1) result[index ++] = nums[deque.getFirst()]; } return result; } }
如果不用队列也可以,思路是一样的,维护一个窗口,当窗口移动之后,检查之前窗口的最大元素是否在移动后的窗口中,如果在只需要比较最大元素与新近的元素就可以;如果不存在就在新窗口中找最大元素。代码如下:
public class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums == null || nums.length == 0) return new int[0]; int[] result = new int[nums.length - k + 1]; int maxIndex = 0; int max = Integer.MIN_VALUE; int index = 0; for(int i = 0; i < result.length; i++) { if(i == 0 || maxIndex == i - 1) { max = Integer.MIN_VALUE; for(int j = i; j < i + k; j++) if(nums[j] > max) { max = nums[j]; maxIndex = j; } }else { if(nums[i + k - 1] > max) { max = nums[i + k - 1]; maxIndex = i + k - 1; } } result[index ++] = max; } return result; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 229Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 231You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 345Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 337Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 458Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 521Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 434Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 623Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 432The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 392Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 522Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 537Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 374All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 866Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 884Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 558Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 604Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 766Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 739You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 635For a undirected graph with tre ...
相关推荐
再判断3位置上的2,由于比1大(也就是队列的尾部比这个数小),所以把队列尾部弹出一个,1弹出,由于4比2大,就可以放2了:再看窗口中减数的逻辑,当L向右移动的时
Maximum 255. Verify Preorder Sequence in Binary Search Tree 907. Sum of Subarray Minimums 二叉搜索树 99. Recover Binary Search Tree 109. Convert Sorted List to Binary Search Tree 116. Populating Next ...
leetcode信封 LeetCode LeetCode解题 源码目录 //main下为源码,test下为单元测试 │ src │ ├─main │ └─java │ └─com │ └─algorithm │ GeneratorParenthesis.java //22. ...Sliding Window Maximum
318| [Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/) | [C++](./C++/maximum-product-of-word-lengths.cpp) [Python](./Python/maximum-product-of-word-...
Model from Sliding Window Counts 34 2.8 Markov Scoring 34 2.9 The ADFGVX Transposition System 47 2.10 CODA 49 2.11 Columnar Transposition Problems 50 CHAPTER 3 MONOALPHABETIC SUBSTITUTION 3.1 ...
Sliding Window,滑动窗口类型 滑动窗口类型的题目经常是用来执行数组或是链表上某个区间(窗口)上的操作。比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始,一直往右边一个一个元素挪动。当然了,...
13.4.1 Sliding Window Lempel–Ziv Algorithm 441 13.4.2 Tree-Structured Lempel–Ziv Algorithms 442 13.5 Optimality of Lempel–Ziv Algorithms 443 13.5.1 Sliding Window Lempel–Ziv Algorithms 443 13.5.2 ...
作业说明 代码注释中有力扣链接. ...滑动窗口最大值, sliding-window-maximum.ts 两两交换链表中的节点, swap-nodes-in-pairs.ts 三数之和, three-sum.ts 接雨水, trapping-rain-water.ts 两数之和,
The normalization is performed over a sliding window that typically spans 301 frames (that is 3 seconds at a typical 100 Hz frame rate). The middle frame in the window is normalized based on the mean ...
滑动窗口的最大值(Maximum_value_of_sliding_window.java) 包含min函数的栈(The_stack_containing_the_min_function.java) 队列的最大值(The_maximum_value_of_the_queue.java) 堆(heap_items) ...
Sliding Window 数据结构 线段树 Cows 线段染色 排队问题 第K大的数 离散化+线段树 灯光投影 网络赛取连续子序列问题 线段树+树状数组+并查集,转化为排队问题 离散化 离散化矩形切割,矩形覆盖面积统计 ...
8.3 Sliding window minimum . . . . . . . . . . . . . . . . . . . . . . . . . 81 9 Range queries 83 9.1 Static array queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 9.2 Binary ...
近来,在野外发现蒙面人脸的方法已经兴起,其应用范围很广,从暴力视频检索到视频监视。 主要由于低分辨率和任意视角的困难以及收集足够数量的训练样本的局限性,其准确检测仍然是一个未解决的问题。...
08.zip Drop down a popdown window instead of a dropdown list from a combobox 在ComboBox中用Drop down方式代替dropdown list方式(32KB)<END><br>9,09.zip Change listbox width of combo boxes 在...