手写算法: 滑动窗口最大值

239. 滑动窗口最大值

思路

理解题意：以 k 为滑动窗口的大小，每次向右滑动一次，都需要比较窗口内的数值，取最大值塞入 res 数组中。

1. 使用单调递增普通队列 q 维护最大值，这样最大值始终在数组的第一位

2. 进行遍历时，要注意队列队头是否在滑动窗口范围内，即 q[0] <= i - k,若不在的话，需要剔除

时间复杂度：O(n)

空间复杂度: O(k), k 为窗口范围

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
  const len = nums.length;
  // 用来储存单调递增的数的下标
  let q = [];
  // 前三个比较特殊，先创建滑动窗口
  for (let i = 0; i < k; i++) {
    // 当q有值，并且当前的数大于上一个数时，需要把上一个数对应的索引剔除，只留大的
    while (q.length && nums[i] >= nums[q[q.length - 1]]) {
      q.pop();
    }
    // 将此时的下标推入q数组中
    q.push(i);
  }

  // 因为q是单调递增的数组，那么第一个下标对应的nums数值肯定是最大的
  let res = [nums[q[0]]];

  for (let i = k; i < len; i++) {
    // 看第一个数值是否还在滑动窗口内，如果不在的话，剔除掉。
    if (q[0] <= i - k) {
      q.shift();
    }
    while (q.length && nums[i] >= nums[q[q.length - 1]]) {
      q.pop();
    }
    q.push(i);
    // 每向右滑动一个窗口，都要将当前窗口最大的值推入数组中
    res.push(nums[q[0]]);
  }
  return res;
};

手写题: 实现 React useMemo 原理

function _useMemo() {
  // 用于存放定时器id
  let timer = null;
  // 用于存放唯一的key
  let key = -1;
  // 用于存放多个memo，用key作为唯一标识
  let map = new Map();

  // 闭包
  return function(fn, deps) {
    key++;

    timer && clearTimeout(timer);
    // 异步操作，同步走完以后，还原key。当组件重新渲染时，又从0开始叠加，这样才能保证每次重新渲染后memo能对上
    timer = setTimeout(() => (key = -1), 100);

    const curKey = key;
    const { deps: lastDeps } = map.get(curKey) || {};

    if (lastDeps) {
      const isChanged = deps.some((item, i) => item !== lastDeps[i]);

      if (isChanged) {
        map.set(curKey, { result: fn(), deps });
        return map.get(curKey).result;
      }
    }
    // useMemo拿的是函数返回的值
    map.set(curKey, { result: fn(), deps });
    return map.get(curKey).result;
  };
}

const useMemo = _useMemo();

export default useMemo;

demo