239. 滑动窗口最大值
一开始没有思路,暴力了,然后果然超时;
看提示中的单调队列没有特别明白;后面反应过来跟单调栈很像;
也确实很符合本题的情况,一旦队尾出现更大的数,前面更小的数就不需要了,
他们不会成为最大数被弹出后的备选。
值得注意的是本题数次出现区间错误，一开始我的操作居然是删除q[l]，插入q[r];
这完全成了左开右闭了,和我定义时的左闭右闭不一样了。
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
//参考思路:单调队列, 队列从队头开始递减;且两端可删除,但只能队尾插入
//自我思路:记录下最大值的位数,(然后最大值弹出后怎么更新呢?)
//暴力:每次遍历滑动窗口内的数值,找出最大数=>然后果然超时了
var maxSlidingWindow = function(nums, k) {
let queue = []
let result = []
let l,r
for(let i = 0; i<k;i++){
while(queue.length>0&&queue[queue.length-1]<nums[i]){
queue.pop()
}
queue.push(nums[i])
}
result.push(queue[0])
//这里要把区间搞明白,举例k=1
for(l = 1,r=k; r< nums.length;l++,r++){//这里区间一开始写成了l=0,r=k-1
if(nums[l-1] == queue[0]){//这里区间一开始写成了l,搞错了
queue.shift()
}
while(queue.length>0&&queue[queue.length-1]<nums[r]){
queue.pop()
}
queue.push(nums[r])
result.push(queue[0])
}
return result
};
347.前 K 个高频元素
js没有堆，手撕太难，暂且跳过
先写一个排序的简易版(没有优化)
堆的结构先放着,二刷再考虑手撕
顺便,感觉自己优化做的好少,可能这就是我小红书笔试一半用例过不去的原因
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
//这个难道不是用堆?
//好吧果然是堆,不是js怎么用啊,手撕?
//嗯,手撕;抄一个吧
var topKFrequent = function(nums, k) {
let map = new Map()
for(let i = 0; i< nums.length;i++){
if(map.has(nums[i])){
map.set(nums[i],map.get(nums[i])+1)
}else{
map.set(nums[i],1)
}
}
let orderEn = Array.from(map.entries()).sort((a,b)=>b[1]-a[1])//应该写降序,写错了成了升序
return orderEn.slice(0,k).map(e=>e[0])
};
class Heap{
constructor(compareFn){
this.compareFn = compareFn
this.queue = []
}
push(item){
}
pop(){
}
size(){
}
compare(){
}
}
栈和队列总结
栈的后进先出的特性，导致其特别适合用来“保留”一些东西；
一方面，反过来说，可以用来消除一些东西（括号，相同项）；
另一方面，可以保存一些中间结果,比如逆波兰表达式等;
更广泛的应用是,可以保留遍历的中间路径,包括递归,树和图的遍历等等;
队列先进先出的特性,则适合对流式的东西,不需要回头,但需要当前会影响到之后的东西作处理;
包括滑动窗口的最大值,bfs,层序遍历等等
顺便,感觉自己总结的很烂,完全没有做到费曼学习法的要求，试想，如果我是新手，我能看懂吗？
博客应当写的更认真才是。认真感觉是我失去了的宝贵的品质之一。