Menu Sidebar
Menu

Leetcode

Find the Duplicate Number

双指针. 找环

 

H-Index

 

Missing Number 位运算

 

Sliding Window Maximum 单调队列解区间最值

经典面试问题, 终于出现在Leetcode了, 写完后看了下discuss, 基本大家写的都差不多. 可见这题多容易考, 我身边的朋友就有被问过这题的. 题目很简单, 就是给一个大小为k的窗口, 然后给一个数组, 问在k下的最值是什么. 就用Leetcode的例子吧.

这题的解法好像有两种, 一种是双指针, 另一种是单调队列, 双指针判断corn case很复杂, 所以用单调队列比较简单, 代码短,面试才不容易出错. 单调队列是一个单调递增(递减)的队列, 这题中, 单调队列的大小为k.需要注意一下几点: 单调队列是一个双向队列, 所以可以用Dequeue 或者直接用LinkedList实现. 添加元素时, 从右(last) 往左(first) 添加, 添加的是数组的index, 因为下边我们需要通过比较index, 来判断是否过期. 添加元素前, 需要删除过期元素, 当判断一个元素是否过期时, 要从前往后判断, 因为前边的元素是队列中时序最”老”的元素. 并且判断时, 要比较最老元素的index和i-k+1的大小. i – k + 1是窗口[i-k+1,i]的最左边的index, 比如, 当i=6, 即在第6个元素时, 窗口左边的index为6-3+1 = 4, 所以窗口内最大可能的元素index为[4,5,6] 添加元素前, 需要删除比当前元素小的元素, 我们需要从队列的右边往左边 踢出元素, […]

Newer Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

March 2021
M T W T F S S
1234567
891011121314
15161718192021
22232425262728
293031