滑动窗口问题的扩展

来源：3-7 滑动窗口 Minimum Size Subarray Sum

qq_往事_8

2019-09-22

老师，如果数组长度为n，滑动窗口长度为k，想要计算各个滑动窗口内的中位数，应该是个什么思路呢

写回答

1回答

liuyubobobo

2019-09-23

把滑动窗口中的元素扔进一个 treeset，由于treeset是有序的，可以通过每次从窗口中删除的元素和添加的元素与当前中位数大小的关系，判断出在新的窗口中，中位数应该往后挪一位，还是往前挪一位。

另外一个比较 tricky 的想法是把窗口中的元素分成两个treeset，小的一半放到一个treeset，大的一半放到另一个treeset，之后要做的事情，只是每次窗口变化的时候，维护这两个treeset，让这两个treeset始终保持小的一半在一堆，大的一半在另一堆，根据这两个treeset，可以很容易的求出中位数。

继续加油！：）

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7408 学习 · 1150 问题

查看课程

相似问题

为什么能用滑动窗口呢

回答 1

关于Leetcode双周赛的一道题

回答 1

不是快慢指针，而是滑动窗口

回答 1

关于LC209优化暴力解的思路

回答 1

LeetCode438-关于滑动窗口问题中while循环内的循环条件

回答 1

打开慕课网App查看更多内容