【LeetCode】239.滑动窗口最大值

题目链接239. 滑动窗口最大值题目描述数据范围1nums.length10^5-10^4nums[i]10^41knums.length思路1采用双指针去维护这个窗口边界同时每次滑动都遍历计算窗口内的最大值这种方式时间复杂度O(n*k)显然时间复杂度比较高数据范围也比较大不太能接受。思路2仍然采用双指针来维护窗口边界主要优化是这个O(K)复杂度的遍历这里可以用一个K大小的大根堆来维护窗口内的最大值这里由于不仅看值还要看下标因此堆中的每个节点可以存储是一个二元组元素下标但仔细一想其实不用我们只需要存储下标就行了堆比较的时候还是按照值来调整下标在堆中的顺序每次滑动窗口将当前的元素下标加入堆中并且检查堆顶元素的下标如果不在窗口内了堆顶下标k i(当前窗口右边界)那么就需要不断移除堆顶元素直到满足当前堆中的最大元素下标在窗口内每次记录答案都直接从堆中取当前的最大值也就是堆顶的值这里调整堆复杂度是O(logK)因此总的复杂度为O(nlogK)golang里面实现堆排主要是需要实现以下几个方法注意push和pop实现是指针方法。Len()Less(i,jint)boolSwap(i,jint)Push(vinterface{})指针Pop()interface{}指针实现1用sort.IntSlice可以少实现两个方法它本身有序// 实现一个大根堆堆顶元素最大,只存储下标即可这里有sort所以我们实现less、push和pop方法即可vara[]inttypehpstruct{sort.IntSlice}func(h hp)Less(i,jint)bool{returna[h.IntSlice[i]]a[h.IntSlice[j]]}func(h*hp)Push(xinterface{}){h.IntSliceappend(h.IntSlice,x.(int))}func(h*hp)Pop()interface{}{old:h.IntSlice n:len(old)res:old[n-1]h.IntSliceold[:n-1]returnres}funcmaxSlidingWindow(nums[]int,kint)[]int{ifk1{returnnums}anums h:hp{make([]int,k)}// 入堆fori:0;ik;i{h.IntSlice[i]i}heap.Init(h)ans:make([]int,0,len(nums)-1)ansappend(ans,nums[h.IntSlice[0]])fori:k;ilen(nums);i{heap.Push(h,i)forh.IntSlice[0]i-k{heap.Pop(h)}ansappend(ans,nums[h.IntSlice[0]])}returnans}实现2用数组实现堆typehp[]int// 记录下标vara[]intfunc(h hp)Less(i,jint)bool{returna[h[i]]a[h[j]]}func(h*hp)Push(xinterface{}){*happend(*h,x.(int))}func(h hp)Len()int{returnlen(h)}func(h hp)Swap(i,jint){h[i],h[j]h[j],h[i]}func(h*hp)Pop()interface{}{old:*h n:len(old)res:old[n-1]*hold[:n-1]returnres}funcmaxSlidingWindow(nums[]int,kint)[]int{ifk1{returnnums}anums h:hp{}// 入堆fori:0;ik;i{heap.Push(h,i)}heap.Init(h)ans:make([]int,0,len(nums)-1)ansappend(ans,nums[(*h)[0]])fori:k;ilen(nums);i{heap.Push(h,i)for(*h)[0]i-k{// 当前最大元素的下标不在区间内则弹出heap.Pop(h)}ansappend(ans,nums[(*h)[0]])}returnans}思路3我们用堆主要是为了维护这个窗口内最大值那么我们换一种思路用一个单调队列维护窗口的最大值顺序我们按照从左往右单调递减。对前k个元素过一遍单调队列的时候队头左边始终保持最大值因此新进一个元素的时候我们只需要和队尾右边的元素比较如果大于队尾的元素就移除掉队尾的元素因此已经没用了。当窗口移动的时候为了保证队列中的元素都在窗口内我们需要检查一下队首元素的下标k的值是否小于等于i如果小于就该去掉队头的元素了。因此队列中元素满足两个特性从左往右值是单调递减的。从做往右下标是单调递增的。我们push的时候只需要按照这两个特定来维护队列即可窗口滑动的时候我们还需要检查队首元素的下标是否在当前窗口内不在就删除队首元素直到在窗口内。每个元素在遍历的时候有且仅会进出一次队列因此实际上时间复杂度为O(n)。funcmaxSlidingWindow(nums[]int,kint)[]int{queue:[]int{}// 单调队列维护下标push:func(iint){forlen(queue)0nums[i]nums[queue[len(queue)-1]]{queuequeue[:len(queue)-1]}queueappend(queue,i)}fori:0;ik;i{push(i)}n:len(nums)ans:make([]int,0,n-k1)ansappend(ans,nums[queue[0]])fori:k;ilen(nums);i{push(i)forqueue[0]i-k{// 删除队头元素queuequeue[1:]}ansappend(ans,nums[queue[0]])}returnans}