- 浏览: 171769 次
- 性别:
- 来自: 济南
文章分类
最新评论
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 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
return [3,3,5,5,6,7]
题目的意思是给定一个数组,一个长度为k的滑动窗口,从数组的最左边滑动到最右边,每次移动一个位置,找出每次窗口中最大的元素。这道题我们可以通过维护一个最大值的下标maxIndex,和一个最大值max来解决。遍历数组,每当窗口滑动后,我们通过最大值的下标来判断最大值元素是否还在窗口中,如果在,就只比较最大值和当前值就可以,做相应的处理;如果最大值元素不在窗口中,那我们就从这个窗口中找出最大值,时间复杂为O(k),这样总的时间复杂度为O(nk)。代码如下:
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
return [3,3,5,5,6,7]
题目的意思是给定一个数组,一个长度为k的滑动窗口,从数组的最左边滑动到最右边,每次移动一个位置,找出每次窗口中最大的元素。这道题我们可以通过维护一个最大值的下标maxIndex,和一个最大值max来解决。遍历数组,每当窗口滑动后,我们通过最大值的下标来判断最大值元素是否还在窗口中,如果在,就只比较最大值和当前值就可以,做相应的处理;如果最大值元素不在窗口中,那我们就从这个窗口中找出最大值,时间复杂为O(k),这样总的时间复杂度为O(nk)。代码如下:
public class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums == null || nums.length == 0) return new int[0]; if(k == 1) return nums; int maxIndex = 0; int max = Integer.MIN_VALUE; int index = 0; int[] result = new int[nums.length - k + 1]; for(int i = 0; i < nums.length - k + 1; 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 221Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 219You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 336Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 325Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 443Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 498Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 423Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 611Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 420The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 378Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 511Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 521Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 364All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 853Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 876Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 547Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 592Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 757Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 724You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 623For 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 在...