RTTO WEEK4
WEEK 4
27.移除元素(e)
slow用于赋值符合条件的fast位置数据,fast碰到不与val相等的则赋值,碰到与val相等的则++
344.反转字符串(e)
上周做过了
236.滑动窗口最大值(h)
需要重写单调队列(由于是求max,入队元素必须遵从单调递减)
三个功能 由STL中deque双端队列容器构造
front() 查询当前单调队列中最大值,由于构造的是单调递减,所以最大值为队首元素 直接front
pop() 查询当前单调队列中需要弹出的值是否是队首的值,若是则pop_front
push() 将不满足单调递减要求的数 pop_back出;若满足单调递减要求,循环push_back直至不满足要求————即要保持单调队列中元素始终单调
使用单调队列时
首先将前k个元素放进队列,res中记录前k个最大值;
后遍历k个后的元素,单调队列pop出首部元素,push入新元素,后进行front计算最大值push_back入res vector直至循环结束;
347.前k个高频元素(m)
涉及到STL库优先队列
1 | priority_queue<Type, Container, Functional> |
Type 是数据类型,Container 是容器类型(Container必须是用数组实现的容器,比如vector,deque等等,但不能用 list。STL里面默认用的是vector),Functional 是比较的方式。
当需要用自定义的数据类型时才需要传入这三个参数,使用基本数据类型时,只需要传入数据类型,默认是大顶堆。
1 | //升序队列,小顶堆 |
71.简化路径(m)
使用栈