Top-K Largest Elements in Every Sliding Window

Problem Statement

You are given an integer array nums, an integer w representing the sliding window size, and an integer k. As the window slides from the leftmost position to the rightmost position one element at a time, you need to identify the k largest elements inside the window.

Return a list of lists, where each inner list contains the k largest elements in the corresponding window, sorted in descending order.

Function Interface

def top_k_sliding_window(nums: list[int], w: int, k: int) -> list[list[int]]:
    pass

Input and Output Format

• Input:
  • nums: A list of integers.
  • w: The width of the sliding window.
  • k: The number of largest elements to retrieve per window.
• Output:
  • A list of lists of integers with length len(nums) - w + 1. Each sublist has length k and is sorted in descending order.

Examples

Example 1

Input: nums = [4, 1, 3, 2, 6, 5], w = 3, k = 2
Output: [[4, 3], [3, 2], [6, 3], [6, 5]]

Explanation:
- Window [4, 1, 3]: top 2 largest are [4, 3]
- Window [1, 3, 2]: top 2 largest are [3, 2]
- Window [3, 2, 6]: top 2 largest are [6, 3]
- Window [2, 6, 5]: top 2 largest are [6, 5]

Example 2

Input: nums = [10, 10, 10, 2], w = 3, k = 1
Output: [[10], [10]]

Explanation:
- Window [10, 10, 10]: top 1 largest is [10]
- Window [10, 10, 2]: top 1 largest is [10]

Constraints

• 1 <= nums.length <= 10^5
• 1 <= w <= nums.length
• 1 <= k <= min(w, 50)
• -10^9 <= nums[i] <= 10^9

Edge Cases to Consider

• Duplicate values within the same sliding window.
• k == 1 (equivalent to the classic sliding window maximum).
• k == w (all window elements must be sorted and returned).