Meta VO 面试真题解析：滑动窗口平均值与有序数组第 k 小元素

Given an array of integers and an integer k, for each element x in the array one can construct a slice of the array that includes x and k - 1 elements before x (k elements in total). This is called a rolling window, and k is called the window size.

Given an array of integers and a window size, write a function that returns the average value for each rolling window.

You have m arrays of sorted integers. The sum of the array lengths is n. Find the kth smallest value of all the values.

这道题里实际上包含了两段经典题目：一段是数组的 rolling window 平均值计算，另一段是多个有序数组中找第 k 小元素。前者通常用滑动窗口维护窗口内元素和，窗口右移时减去左端、加上新元素，时间复杂度可做到 O(n)；后者更适合用最小堆或二分分治，在 m 个有序数组的首元素中维护当前最小值，逐步弹出直到找到第 k 小，常见做法能把复杂度控制在 O(k log m) 或更优。