Amazon OA 面试题解析：滑动窗口第 k 小值（Find the kth Minimum Vulnerability）

Amazon Web Services has n servers where the vulnerability score of the i-th server is vulnerability[i]. A client wants to deploy their application on a group of m contiguous servers. The vulnerability of a group is defined as the kth minimum vulnerability among the chosen servers.

Find the vulnerability of each possible group of m contiguous servers the client can choose.

Example

k = 2
m = 3
vulnerability = [1, 3, 2, 1]

There are 2 contiguous groups of m = 3 servers: [1, 3, 2] and [3, 2, 1].

The 2nd lowest vulnerability in each group is 2.

Return the answers for each group, in order: [2, 2].

Function Description

Complete the function findKthMinimumVulnerability in the editor below.

findKthMinimumVulnerability has the following parameter(s):

• int k: the order of the vulnerability to find
• int m: the number of servers in a group
• int vulnerability[n]: the vulnerabilities of each server

Returns:

int[n - m + 1]: the ith element represents the kth minimum vulnerability among the vulnerabilities of the ith contiguous group.

这道题本质上是一个固定窗口长度为 m 的滑动窗口问题，但窗口内要求输出第 k 小元素。对于每个连续子数组，都要快速求出其中的第 k 小值，通常需要借助可维护有序结构，例如双堆、平衡树、Fenwick Tree 或线段树配合坐标压缩。题目示例中，窗口 [1, 3, 2] 和 [3, 2, 1] 的第 2 小值都为 2，因此答案是 [2, 2]。在实现时关键是支持窗口右移后元素的插入与删除，并能在每一步高效定位第 k 小元素，避免对每个窗口都完整排序导致超时。