数组要开多大
数组模拟单调队列求 n 个数的滑窗最值,数组 q【0】。 本节模型:window_max_arr 不用 std::deque,用数组 q 加 head、tail 两个下标模拟两端操作。
std::deque 两端操作多快
std::deque 的 push_back、pop_front 这些两端操作,时间复杂度是【0】。
数组模拟的窗口最大
运行下面这段程序: 本节模型:window_max_arr 不用 std::deque,用数组 q 加 head、tail 两个下标模拟两端操作。 #include <algorithm> #include <deque&
两种写法结果一致吗
运行下面这段程序: 本节模型:window_max_arr 不用 std::deque,用数组 q 加 head、tail 两个下标模拟两端操作。 #include <algorithm> #include <deque&
补全:数组版队尾维护
补全 window_max_arr:队尾(q[tail-1])不比 a[i] 大的都弹掉。补全后输出每个窗口的最大值。 本节模型:window_max_arr 不用 std::deque,用数组 q 加 head、tail 两个下标模拟两端
补全:数组版队首过期
补全 window_max_arr:队首下标滑出窗口就 head++。补全后输出每个窗口的最大值。 本节模型:window_max_arr 不用 std::deque,用数组 q 加 head、tail 两个下标模拟两端操作。 (本题用 g
补全:数组版入队
补全 window_max_arr:把当前下标 i 放到队尾。补全后输出每个窗口的最大值。 本节模型:window_max_arr 不用 std::deque,用数组 q 加 head、tail 两个下标模拟两端操作。 (本题用 g++ -
补全:数组版求最小
补全 window_min_arr:求最小,要弹掉队尾不比 a[i] 小的。补全后输出每个窗口的最小值。 本节模型:window_max_arr 不用 std::deque,用数组 q 加 head、tail 两个下标模拟两端操作。 (本题
补全:一百万个数的累加
补全:用数组版单调队列算 100 万个数(窗口长 100)的窗口最大值之和。和会远远超过 int 的上限,累加器要选对类型。 本节模型:window_max_arr 不用 std::deque,用数组 q 加 head、tail 两个下标模
改成求最小弹掉谁
把 window_max 改成求最小,只需把队尾维护改成弹掉值【0】的下标。 本节模型:window_max / window_min 用 std::deque 存下标做单调队列,求每个长度为 k 的窗口的最值。