【题目】 有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
例如，数组为[4，3，5，4，3，3，6，7]，窗口大小为3时：
[4 3 5] 4 3 3 6 7 窗口中最大值为5
4 [3 5 4] 3 3 6 7 窗口中最大值为5
4 3 [5 4 3] 3 6 7 窗口中最大值为5
4 3 5 [4 3 3] 6 7 窗口中最大值为4
4 3 5 4 [3 3 6] 7 窗口中最大值为6
4 3 5 4 3 [3 6 7] 窗口中最大值为7
如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。
请实现一个函数。
输入：整型数组arr，窗口大小为w。
输出：一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。
以本题为例，结果应该返回{5，5，5，4，6，7}。
解答:本题以一个qmax双端队列来实现窗口最大值的更新,qmax需要处理一下三个问题:
qmax存放arr下标，队头的元素是当前窗口的最大值。
1.qmx如果有小于arr[i],弹出小于arr[i]的值
2.qmax队尾入队
3.qmax及时清理过期的值
代码实现
/*
qmax双端队列:队头是最大值
队尾最小值弹出，队头过期值弹出
*/
- (NSArray*)getMaxWindow:(NSArray*)arr w:(NSInteger)w{
if(!arr || w<1|| arr.count<2) {
returnnil;
}
DoubleQueue * qmax = [DoubleQueue new];//存放arr下标
NSMutableArray * res = [NSMutableArray arrayWithCapacity:arr.count-w+1];
NSIntegerindex =0;
for(inti =0; i
while(![qmaxisEmpty] && [arr[[qmax.peekLastintegerValue]]integerValue]<=[arr[i]integerValue]) {
[qmaxpollLast];//把队尾的最小值弹出,队列中已是窗口最大值
}
[qmaxaddLast:[NSStringstringWithFormat:@"%d",i]];
if([qmax.peekFirstintegerValue] == i-w) {//qmax对头下标已过期，弹出当前下标
[qmaxpollFirst];
}
if(i>=w-1) {//产生最大值结果了
res[index++]=arr[[qmax.peekFirstintegerValue]];//队头是最大值
}
}
returnres;
}
双端队列实现
@interface DoubleQueue()
@property (nonatomic,strong) NSMutableArray * queueArray;
@end
@implementation DoubleQueue
#pragma mark - public method
- (void)addLast:(NSString*)element{
[self.queueArrayaddObject:element];
}
- (void)addFirst:(NSString*)element{
[self.queueArray insertObject:element atIndex:0];
}
- (NSString*)pollLast{
NSString* element =self.queueArray.lastObject;
[self.queueArray removeLastObject];
returnelement;
}
- (NSString*)pollFirst{
NSString* element =self.queueArray.firstObject;
[self.queueArray removeObjectAtIndex:0];
returnelement;
}
- (BOOL)isEmpty{
returnself.queueArray.count==0;
}
- (NSString*)peekLast{
return self.queueArray.lastObject;
}
- (NSString*)peekFirst{
return self.queueArray.firstObject;
}
#pragma mark - getter
- (NSMutableArray*)queueArray{
if (!_queueArray) {
_queueArray= [[NSMutableArrayalloc]init];
}
return _queueArray;
}
@end
qmax队列入队出队流程
以题目给的例子为例:数组为[4，3，5，4，3，3，6，7]，窗口大小为3时：
当i=0;0入队，qmax队列中有 0
当i=1;1入队，qmax队列中有 0 1
当i=2;i=1弹出，i=0弹出, 2入队 ,qmax队列中有 2，窗口最大值arr[2]=5
当i=3;3入队 ，qmax队列中有 2 3，窗口最大值arr[2]=5
当i=4;4入队 ，qmax队列中有 2 3 4,窗口最大值arr[2]=5
当i=5;5入队， qmax队列中有 2 3 4 5，i=2过期弹出队列，窗口最大值arr[3]=4
当i=6;i=5弹出队列，i=4弹出队列，i=3弹出队列，6入队列, qmax队列中有 6，窗口最大值arr[6]=6
当i=7;i=6弹出队列,i=7入队列,窗口最大值arr[7]=7
算法来自:《程序员代码面试指南:IT名企算法与数据结构题目最优解》
