[2,3,4,2,6,2,5,1],3
[4,4,6,6,6,5]
[9,10,9,-7,-3,8,2,-6],5
[10,10,9,8]
[1,2,3,4],5
[]
给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。
比较简单的思路是每次用一个ArrayList来存放窗口内的数,进行排序,然后得到最大的添加进外面的ArrayList中,最后返回。
public class Solution {
public ArrayList maxInWindows(int [] num, int size)
{
List result = new ArrayList();
if(num.length == 0 || size == 0)
return (ArrayList)result;
for(int i=0;i<=num.length-size;i++){
List list = new ArrayList();
for(int j=i;j<i+size;j++){
list.add(num[j]);
}
Collections.sort(list);
result.add(list.get(size-1));
}
return (ArrayList)result;
}
}
遍历再排序,时间复杂度还是挺高的,遍历一遍是不可避免的,优化点在于如何以O(1)的时间复杂度拿到当前窗口的最大值。下面介绍一下优化方法。
以输入数字{2,3,4,2,6,2,5,1}为例一步分析。
数组的第一个数字是 2,把它存入队列中。第二个数字是3.由于它比前一个数字 2 大,因此 2不可能成为滑动窗口中的最大值。2 先从队列里删除,再把3存入到队列中。此时队列中只有一个数字 3。针对第三个数字 4 的步骤类似,最终在队列中只剩下一个数字 4。此时滑动窗口中已经有 3 个数字,而它的最大值 4 位于队列的头部。
接下来处理第四个数字 2。2 比队列中的数字 4 小。当 4 滑出窗口之后 2 还是有可能成为滑动窗口的最大值,因此把 2 存入队列的尾部。现在队列中有两个数字 4 和 2,其中最大值 4 仍然位于队列的头部。
下一个数字是 6。由于它比队列中已有的数字 4 和 2 都大,因此这时 4 和 2 已经不可能成为滑动窗口中的最大值。先把 4 和 2 从队列中删除,再把数字 6 存入队列。这个时候最大值 6 仍然位于队列的头部。
第六个数字是 2。由于它比队列中已有的数字 6 小,所以 2 也存入队列的尾部。此时队列中有两个数字,其中最大值 6 位于队列的头部。
接下来的数字是 5。在队列中已有的两个数字 6 和 2 里,2 小于 5,因此 2 不可能是一个滑动窗口的最大值,可以把它从队列的尾部删除。删除数字 2 之后,再把数字 5 存入队列。此时队列里剩下两个数字 6 和 5,其中位于队列头部的是最大值 6。
数组最后一个数字是 1,把 1 存入队列的尾部。注意到位于队列头部的数字 6 是数组的第 5 个数字,此时的滑动窗口已经不包括这个数字了,因此应该把数字 6 从队列删除。那么怎么知道滑动窗口是否包括一个数字?应该在队列里存入数字在数组里的下标,而不是数值。当一个数字的下标与当前处理的数字的下标之差大于或者等于滑动窗口的大小时,这个数字已经从滑动窗口中滑出,可以从队列中删除了。
框框里的都是下标。
import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
public ArrayList maxInWindows(int [] num, int size)
{
//存放当前窗口中最大值
ArrayList res = new ArrayList();
//队列的头部存放的是当前窗口最大值
LinkedList queue = new LinkedList();
if(num == null || num.length <= 0 || size <= 0){
return res;
}
for(int i=0;i<num.length;i++){
//比如当前数据比队尾的数字大,说明当前这个数字最起码在从现在起到后面的过程中可能是最大值
//而之前队尾的数字不可能最大了,所以要删除队尾元素。
while(!queue.isEmpty() && num[queue.peekLast()] < num[i]){
queue.pollLast();
}
queue.add(i);
//队头的元素是否超过窗口的范围
if(queue.peekFirst() == i-size){
queue.pollFirst();
}
//在包含了三个元素之后才开始记录,其中最大值就在队列的头部
if(i >= size - 1){
res.add(num[queue.peekFirst()]);
}
}
return res;
}
}
package StackAndQueue;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
/**
* 滑动窗口的最大值
* 给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。
*/
public class Solution52 {
public static void main(String[] args) {
Solution52 solution52 = new Solution52();
int[] num = {2, 3, 4, 2, 6, 2, 5, 1};
int size = 3;
ArrayList list = solution52.maxInWindows(num, size);
System.out.println(list);
}
/**
* 最大堆方法
* 构建一个窗口size大小的最大堆,每次从堆中取出窗口的最大值,随着窗口往右滑动,需要将堆中不属于窗口的堆顶元素删除。
*
* [@param num
* @param size
* @return](/profile/547241) */
public ArrayList maxInWindows_2(int[] num, int size) {
ArrayList res = new ArrayList();
if (size > num.length || size < 1) return res;
// 构建最大堆,即堆顶元素是堆的最大值。
PriorityQueue heap = new PriorityQueue((o1, o2) -> o2 - o1);
for (int i = 0; i < size; i++) heap.add(num[i]);
res.add(heap.peek());
for (int i = 1; i + size - 1 < num.length; i++) {
heap.remove(num[i - 1]);
heap.add(num[i + size - 1]);
res.add(heap.peek());
}
return res;
}
/**
* 双队列方法
* 滑动窗口的最大值总是保存在队列首部,队列里面的数据总是从大到小排列。
*
* [@param num
* @param size
* @return](/profile/547241) */
public ArrayList maxInWindows(int[] num, int size) {
ArrayList res = new ArrayList();
if (num == null || num.length == 0 || size == 0 || size > num.length) {
return res;
}
Deque deque = new LinkedList();
for (int i = 0; i < num.length; i++) {
if (!deque.isEmpty()) {
// 如果队列头元素不在滑动窗口中了,就删除头元素
if (i >= deque.peek() + size) {
deque.pop();
}
// 如果当前数字大于队列尾,则删除队列尾,直到当前数字小于等于队列尾,或者队列空
while (!deque.isEmpty() && num[i] >= num[deque.getLast()]) {
deque.removeLast();
}
}
deque.offer(i); // 入队列
// 滑动窗口经过一个滑动窗口的大小,就获取当前的最大值,也就是队列的头元素
if (i + 1 >= size) {
res.add(num[deque.peek()]);
}
}
return res;
}
}
class Solution {
public:
//只考虑两端增删变化的影响
int MaxinW(const vector& num, int low, int high)
{
int MaxVal = INT_MIN;
for (int j = low; j <= high; j++)
MaxVal = max(num[j], MaxVal);
return MaxVal;
}
vector maxInWindows(const vector& num, unsigned int size)
{
vectorres;
int len=num.size();
if (len len)return res;
int MaxVal = MaxinW(num, 0, size - 1); res.push_back(MaxVal);
for (int low = 1, high = size; high < len; low++,high++)
{
if (num[high] >= MaxVal)
MaxVal = num[high];
if (num[low - 1] == MaxVal)
MaxVal = MaxinW(num, low, high);
res.push_back(MaxVal);
}
return res;
}
};
2.参考牛友
class Solution {
public:
//双端队列
//时间复杂度o(n),空间复杂度为o(n)
//deque s中存储的是num的下标
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int>res;
deque<int>s;
int len=num.size();
if (len <= 0||size<=0||size>len)return res;
for (int i = 0;i < len; i++)
{
while (!s.empty() && num[s.back()] <= num[i])//当前值比队列从后往前的大,成为下一个待选值
s.pop_back();
while (!s.empty()&&i - s.front() + 1>size)//最大值已不在窗口中
s.pop_front();
s.push_back(i);
if (i + 1 >= size)//当滑动窗口首地址i大于等于size时才开始写入窗口最大值
res.push_back(num[s.front()]);
}
return res;
}
};
# -*- coding:utf-8 -*- class Solution: def maxInWindows(self, nums, k): # write code here if not k or k>len(nums):return [] cur_max = max(nums[:k]) max_nums = [cur_max] for i in range(0, len(nums) - k): if nums[i] == cur_max: cur_max = max(nums[i + 1:i + k + 1]) elif nums[i + k] > cur_max: cur_max = nums[i + k] max_nums.append(cur_max) return max_nums
双端队列,两端删除添加可用数组模拟。
push/pop操作最后
unshift/shift操作最前
function maxInWindows(num, size) { // 双端队列(两端都可以实现插入和删除) // 队列首位永远是最大值 // 每次进来一个数,依次和前面的数比较,如果进来的数大,则前面的数直接弹出(在后面不可能最大) // 如果进来的数小,则比较下标,下标不存在的将其删除 // 数组实现双端队列,arr存的是下标,arr[0]存最大值下标 var arr = []; // 结果数组 var res = []; if (size === 0) { return res; } for (var i = 0; i < num.length; i++) { // 从第一个开始循环(可以理解成滑动窗口右侧从第一个移动到最后一个) // 进来一个数,依次从最后一个数开始比较 while (arr.length > 0 && num[i] > num[arr[arr.length-1]]) { // 如果进来的数比最后一个大,则将最后一个踢出去,pop arr.pop(); } arr.push(i); // 再判断前面的数是否超了,由于每次进来的数如果更大,则将前面的踢出去,导致arr[0]的下标永远在最前面 if (i - arr[0] + 1 > size) { arr.shift(); } if (i >= size - 1) { res.push(num[arr[0]]); } } return res; } var res = maxInWindows([2,3,4,2,6,2,5,1], 3); console.log(res);
function maxInWindows(num, size) { // write code here if(!num){ return null; } var len = num.length; var arr = []; if(size > len || size <= 0){ return arr; } if(size == 1){ return num; } if(size == len){ //注意这里用Math.max()的时候,如果直接传的是数组名,要在前面加...符号,不然不成功 arr.push(Math.max(...num)); return arr; } for(var i = 0;i < len - size + 1;i++){ var num1 = []; num1 = num.slice(i,i+size); arr.push(Math.max(...num1)); } return arr; } if好像写的有点多~
# -*- coding:utf-8 -*- class Solution: def maxInWindows(self, num, size): #双端队列维护从大到小元素的索引 #步骤 #每遇到一个元素,从后往前将队列中小于该元素的索引全部弹出 #(因为在滑动窗口长度内,小于该元素的值不可能成为最大值,1是该元素在他们后面,2是该元素值比他们大) if size>len(num) or size<1: return [] from collections import deque queue = deque() res = [] for index,val in enumerate(num): #队列为空时加入第一个元素 if index==0: queue.append(index) else: #判断队首是否滑出了窗口 if index-queue[0]==size: queue.popleft() #为当前元素在队列中找到相应位置,其后所有元素弹出 while queue and num[index]>=num[queue[-1]]: queue.pop() queue.append(index) print(queue) #当滑动窗口大小==size时,可以开始记录最大值 if index>=size-1: res.append(num[queue[0]]) return res
/* 表达不清楚的地方,请各位批评指正! 这道题可以用双向队列解决(就是头尾都可以push,pop的队列) 时间复杂度 O(N) 方法如下几点: 1.当我们遇到新数时候,将新的数和双向队列的末尾比较, 若果末尾比新数小,则把末尾pop_back, 直到末尾比新数大或者队列为空才停止; 2.这样就保证队列元素是从头到尾降序的, 由于队列里只有窗口内的数,所以它们其实是窗口内 第一大,第二大…的数。 3.保持队列里只有窗口大小的数的方法是, 右边进一个,左边出一个。 4.由于队列加新数时,已经删除了部分没用的数, 所以队列头的数并不一定是窗口最左的数, 这里有个小技巧,就是队列中存原数组的下标, 这样既可以得到这个数,也可以判断是否是窗口 左边的数了。 */ class Solution { public: vector<int> maxInWindows(const vector<int>& num, unsigned int size) { vector<int> ret; if(num.empty() || size == 0) return ret; deque<int> deq; for(unsigned int i = 0;i < num.size(); ++i){ //每当新数进来时,如果队列头部的下标是窗口最左边的下标,则删除队列头 if(!deq.empty() && deq.front() < i - size) deq.pop_front(); //队列中加入新数 deq.push_back(i); //队列头部就是该窗口最大的! if((i + 1) >= size) ret.push_back(num[deq.front()]); } return ret; } };
int maxValue(int arr[], int begin, int window){ int max = INT_MIN; int end = begin + window; for(int i = begin; i < end; i++){ if(max < arr[i]){ max = arr[i]; } } return max; } vector<int> windowValue(int arr[], int n, int window){ vector<int> result; int end = n - window + 1; for(int i=0; i < end; i++){ result.push_back(maxValue(arr, i, window)); } return result; }
import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { if(num == null || size == 0 || size > num.length) { return new ArrayList<Integer>(); } int windowNum = num.length - size + 1; LinkedList<Integer> list = new LinkedList<>(); ArrayList<Integer> res = new ArrayList<>(); int maxTmp = Integer.MIN_VALUE; for(int i = 0; i < windowNum; i++) { maxTmp = num[i]; for (int j = 1; j < size; j++) { maxTmp = num[i+j] > maxTmp ? num[i+j] : maxTmp; } res.add(maxTmp); } return res; } }
#python2.7 O(n) 时间24ms 内存5760k class Solution: def maxInWindows(self, num, size): # write code here length = len(num) if size<=0 or size>length:return [] i = 0 ans =[max(num[:size])] while size+i < length: if num[i]<ans[-1]: ans.append(max([ans[-1],num[i+size]])) else: ans.append(max(num[i+1:i+size+1])) i+=1 return ans
public ArrayList<Integer> maxInWindows(int[] num, int size) { ArrayList<Integer> maxWindows = new ArrayList<>(); // 特殊情况处理 if (num.length == 0 || num == null || num.length < size) { return maxWindows; } if (num.length >= size && size >= 1) { // 用来保存可能是滑动窗口最大值的数字的下标 ArrayDeque<Integer> indexDeque = new ArrayDeque<>(); for (int i = 0; i < size; i++) { // 如果已有数字小于待存入的数据, // 这些数字已经不可能是滑动窗口的最大值 // 因此它们将会依次地从队尾删除 while (!indexDeque.isEmpty() && num[i] >= num[indexDeque.getLast()]) { indexDeque.pollLast(); } indexDeque.addLast(i); } for (int i = size; i < num.length; i++) { maxWindows.add(num[indexDeque.getFirst()]); // 如果已有数字小于待存入的数据, // 这些数字已经不可能是滑动窗口的最大值 // 因此它们将会依次地从队尾删除 while (!indexDeque.isEmpty() && num[i] >= num[indexDeque.getLast()]) { indexDeque.pollLast(); } // 如果队列的头部元素已经从滑动窗口里滑出,滑出的数字需要从队列的头部删除 if (!indexDeque.isEmpty() && indexDeque.getFirst() <= (i - size)) { indexDeque.pollFirst(); } indexDeque.addLast(i); } maxWindows.add(num[indexDeque.getFirst()]); } return maxWindows; }
import java.util.ArrayList; import java.util.Arrays; public class Solution { ArrayList<Integer> maxInWindows(int [] num, int size) { int[] m_Seq=new int[size]; ArrayList m_MaxSet=new ArrayList(); if (num.length < size) return m_MaxSet; if (size==0) return m_MaxSet; for(int i=0;i<=num.length-size;i++){ m_Seq = Arrays.copyOfRange(num,i,i+size); Arrays.sort(m_Seq); m_MaxSet.add(m_Seq[m_Seq.length-1]); } return m_MaxSet; } }
import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { ArrayList<Integer> list=new ArrayList<Integer>();//用来放每个滑窗的max if(num.length==0||size==0){return list;} for(int i=0;i<=num.length-size;i++){ int[] arr=new int[size]; int j=0,k=i; while(j<=size-1){ arr[j++]=num[k++]; } list.add(Max(arr)); } return list; } public int Max(int[] array){ int max=array[0]; for(int i=0;i<=array.length-1;i++){ if(array[i]>max){ max=array[i]; } } return max; } }
双端队列
时间复杂度:O(n) 空间复杂度:O(k) k为窗口大小
class Solution: def maxInWindows(self , num: List[int], size: int) -> List[int]: res = [] dq = [] for i in range(len(num)): while dq and num[dq[-1]] < num[i]: dq.pop() dq.append(i) if i - dq[0] >= size: dq.pop(0) if i + 1 >= size: res.append(num[dq[0]]) return res
function maxInWindows(num, size) { if(num.length<size||size===0) return [] //第一个最大的 let max=Math.max(...num.slice(0,size)) let maxlist=[max] for(let i=size;i<num.length;i++){ //大于最大值就记录 if(num[i]>max){ max=num[i] } //左边界是最大就重新计算最大值 else if(max==num[i-size]) max=Math.max(...num.slice(i-size+1,i+1)) maxlist.push(max) } return maxlist }
class Solution: def maxInWindows(self , num: List[int], size: int) -> List[int]: # write code here # 不满足条件时为空 if size==0&nbs***bsp;len(num)<size: return [] # 可以生成的组数 groups=len(num)+1-size res=[] for i in range(groups): # i:size+i保证每次取size个大小 res.append(max(num[i:size+i])) return res
class Solution { public: vector<int> maxInWindows(const vector<int>& num, unsigned int size) { vector<int> vec; for(int i=0;i+size-1<num.size();i++){ int x = num[i]; for(int j=i;j<=i+size-1;j++){ x = max(num[j],x); } vec.push_back(x); } return vec; } };
import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int[] num, int size) { ArrayList<Integer> ret = new ArrayList<Integer>(); if( size == 0 || size > num.length){ return ret; } // 暴力解:直接算 for(int i=0; i< num.length-size+1;i++){ int window[] = Arrays.copyOfRange(num,i,i+size); Arrays.sort(window); ret.add(window[size-1]); } return ret; } }
import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int[] num, int size) { // 解法2: 大根堆维护栈顶最大 ArrayList<Integer> ret = new ArrayList<Integer>(); // 边界 if( size == 0 || size > num.length){ return ret; } // 定义大根堆代表滑动窗口 PriorityQueue<Integer> bHeap = new PriorityQueue<Integer>((o1,o2) -> o2-o1); // 大根堆初始化,长度为size-1 for(int i = 0; i<size-1; i++){ bHeap.offer(num[i]); } // 逐个窗口遍历 for(int i=0; i< num.length-size+1;i++){ // 先将当前区间最后一个入队,补足堆长度 bHeap.offer(num[i+size-1]); // 取区间段最大值 ret.add(bHeap.peek()); // 区间首个元素出队,保证堆的长度永远缺1 bHeap.remove(num[i]); } return ret; } }
import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { // 解法3:单调队列(一个非严格递减的队列,想办法保证队首是整个队列的最大值,这样每次取最大值的时间复杂度就是O(1)) // 定义返回 ArrayList<Integer> arr = new ArrayList<>(); // 边界值 if( size==0 || size > num.length){ return arr; } // 单调队列需要deque实现 Deque<Integer> deque = new LinkedList<>(); // 分为2段解决,一段是窗口用于初始化窗口,一段正式计算 // 第一段,初始化窗口(只需要考虑队尾加元素) for(int i=0;i<size;i++){ // 如果新入队的元素大于队尾元素,就删掉队尾,如此迭代,直到找到一个队尾>=新元素,或者到最后都没找到,也就是队列为空 while(!deque.isEmpty() && deque.getLast()<num[i]){ deque.removeLast(); } // 循环结束后,新元素会插到一个不比它小的元素后面(或者直接成为队首),以此规律维护单调队列的递减性 deque.addLast(num[i]); } // 第二段,窗口已经生成,开始迭代。每次都将当前单调队列队首加入返回list,并为右移窗口为下轮迭代准备 for(int i=0;i<num.length-size+1;i++){ // 单调队列队首元素就是当前窗口最大值 arr.add(deque.getFirst()); // 取完元素,单调队列开始右移,为下次做准备,如果下个窗口的屁股即将溢出,break if(i+size==num.length){ break; } // 如果单调队列当前队首==当前元素(也就是窗口最左边的元素),说明最大元素在下一轮会移出窗口,单调队列也需要删除它 if(deque.getFirst()==num[i]){ deque.removeFirst(); } // 然后准备迎接新元素,和第一段剩下的一样 while(!deque.isEmpty() && deque.getLast()<num[i+size]){ deque.removeLast(); } // 循环结束后,新元素会插到一个不比它小的元素后面(或者直接成为队首),以此规律维护单调队列的递减性 deque.addLast(num[i+size]); } return arr; } }