time

主要内容今天的主要内容是深入了解栈和队列中比较难的题录类型滑动窗口最大值与前

239.

的滑动窗口从数组的最左侧移动到数组的最右侧。

你只可以看到在滑动窗口内的

输入:

为了实现实现上述目标因此需要创建出一个这样的队列放进去窗口里的元素然后随着窗口的移动队列也一进一出每次移动之后队列告诉我们里面的最大值是

class

其实队列没有必要维护窗口里的所有元素只需要维护有可能成为窗口里最大值的元素就可以了同时保证队列里的元素数值是由大到小的。

看看下面的动画演示

此时单调队列里维护着

等于单调队列的出口元素那么队列弹出元素否则不用任何操作void

poll(int

{deque.removeLast();}deque.add(value);}

返回队列最大值int

k]);queue.add(nums[i]);zu[count]

queue.peek();}return

返回负数形参中第一个参数排在前面返回正数形参中第二个参数排在前面*

对于队列排在前面意味着往队头靠*

对于堆使用PriorityQueue实现从队头到队尾按从小到大排就是最小堆小顶堆*

从队头到队尾按从大到小排就是最大堆大顶堆---队头元素相当于堆的根节点*

class

{//key为数组元素值,val为对应出现次数MapInteger,Integer

mapnew

num:nums){//计算数字出现的频率map.put(num,map.getOrDefault(num,0)1);}//出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)PriorityQueueint[]

new

PriorityQueue((pair1,pair2)-pair1[1]-pair2[1]);for(Map.EntryInteger,Integer

entry:map.entrySet()){//小顶堆只需要维持k个元素有序if(pq.size()k){//小顶堆元素个数小于k个时直接加pq.add(new

int[]{entry.getKey(),entry.getValue()});}else{if(entry.getValue()pq.peek()[1]){//当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)pq.poll();//弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了pq.add(new

int[]{entry.getKey(),entry.getValue()});}}}int[]

temnew

ik-1;i-1;i--){tem[i]pq.poll()[0];}return

tem;}

陷阱1栈是容器适配器底层容器使用不同的容器导致栈内数据在内存中不一定是连续分布的。

陷阱2缺省情况下默认底层容器是

deque

每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中然后递归返回的时候从栈顶弹出上一次递归的各项参数所以这就是递归为什么可以返回上一层位置的原因。