Articul OA 面试真题解析：Moving Median 滑动窗口中位数

Moving Median

Given an array of integers, return the moving median for each element based on the element and its N-1 predecessors, where N is the sliding window size.

The final output should be a string with the moving median corresponding to each entry in the original array, separated by commas.

Note that for the first few elements, until the window size is reached, the median is computed on a smaller number of entries.

For example: if arr = [3, 1, 3, 5, 10, 6, 4, 3, 1], then your program should output 3,2,3,3,3,5,5,4,4.

Examples

• [5, 2, 4, 6] → 2,3,4
• [3, 0, 0, -2, 0, 2, 0, -2] → 0,0,0,0,0,0,0

这道题要求你对数组做滑动窗口中位数统计：从第 1 个元素开始，当前位置只看它和前面的若干个元素，窗口不足时就用当前已有的更小窗口计算中位数；随着位置推进，窗口扩大到固定大小后，就始终对最近 N 个元素求中位数，并按原数组顺序输出，用逗号连接。实现时最直接的思路是维护窗口内元素并排序取中位数，适合面试中先写出正确解；如果追求更高效率，可以用双堆或有序结构来支持动态插入和删除。