Deque

可以从前面push/pop，可以从尾端push/pop

  • offer(), addFirst, offerFirst, addLast, offerLast
  • peekFirst(), pollFrist
  • peekLast(), pollLast()

Sliding Window Maximum

  • naive: O(nk)，双层循环，其实有一部分的大小关系已经计算过了
  • 然后考虑Sliding window 可以理解为加入一个元素，再删除一个元素，那么内层的for k的循环，可以通过使用HashHeap优化为O(logk),所以总的复杂度变为O(nlogk)
  • 继续优化的话，只可能往O(n)优化，需要采用特殊的数据结构 Deque
    • 把可能成为某个window的max的值留在deque里，而这个deque一定是递减的
    • 所以步骤为
      1. remove 看是否需要删除
      2. add 加入
      3. top 获取最大值(永远在deque的头）
  • 判断时间复杂度的时候，要整体来看，每个点被加入和减去一次，虽然某一步可能需要k部操作，但是一旦前面的点被移除，后面就不可能再遇到。一定会是小于k

results matching ""

    No results matching ""