数据包优先级窗口查找

华为OD新系统机试真题 华为OD新系统上机考试真题 5月13号 100分题型

更多语言题解可点击查看：华为OD机试新系统真题 - 数据包优先级窗口查找(C/C++/Py/Java/Js/Go)题解

华为OD机试新系统真题目录点击查看: 华为OD机试真题题库目录｜机考题库 + 算法考点详解

题目内容

给定 $n$ 个数据包，每个数据包包含 $id$ 和 $priority$。维护一个大小为 $k$ 的滑动窗口，对于每个窗口，找出窗口内每个数据包右边第一个 $priority$ 更高的数据包 $id$。

输入描述

• $n$: 数据包数量 ($1\le n\le 10^6$)
• $k$: 窗口大小 ($1\le k\le 100$)
• $packets$: 数据包内容，长度为 $n$ 的数组，每个元素格式为 $id:priority$
  数据包格式:
• 格式: $<id>:<priority>$
• $id$: 唯一标识符 ($1\le id\le 10^9$)
• $priority$: 优先级 ($1\le priority\le 10^9$)，数值越大优先级越高
  处理规则:
• 窗口滑动: 从左到右滑动，每次窗口包含 $k$ 个连续数据包
• 每个窗口的处理:
• 向右查找第一个 $priority$ 更高的数据包
• 找到 → 记录该数据包的 $id$
• 未找到 → 不记录
• 跳过条件: 数据包不足以构成完整窗口 (窗口大小 $k>$ 数据包总数 $n$) $\to$ 跳过该窗口 窗口内未找到任何 $priority$ 更高的数据包 $\to$ 跳过该窗口

输出描述

输出所有未跳过窗口的结果序列，每个序列包含该窗口内找到的所有"下一个更高优先级数据包 $id$"

样例1

输入

5
3
1:5 2:3 3:7 4:6 5:4

输出

3,3 3

说明

窗口 $[0,2]$: 数据包为 $[1:5,2:3,3:7]$
$1:5$ 后面第一个优先级更高的是 $3:7$，输出 $3$
$2:3$ 后面第一个优先级更高的是 $3:7$，输出 $3$
$3:7$ 后面没有优先级更高的，不输出
该窗口输出: $3$ $3$
窗口 $[1,3]$: 数据包为 $[2:3,3:7,4:6]$
$2:3$ 后面第一个优先级更高的是 $3:7$，输出 $3$
$3:7$ 后面没有优先级更高的，不输出
$4:6$ 后面没有优先级更高的，不输出
该窗口输出: $3$
窗口 $[2,4]$: 数据包为 $[3:7,4:6,5:4]$
$3:7$ 后面没有优先级更高的，不输出
$4:6$ 后面没有优先级更高的，不输出
$5:4$ 后面没有优先级更高的，不输出
该窗口无输出

样例2

输入

4
3
1:1 2:2 3:3 4:4

输出

2,3 3,4

说明

窗口 $[0,2]$: 数据包为 $[1:1,2:2,3:3]$
$1:1$ 后面第一个优先级更高的是 $2:2$，输出 $2$
$2:2$ 后面第一个优先级更高的是 $3:3$，输出 $3$
$3:3$ 后面没有优先级更高的，不输出
输出: $2$ $3$
窗口 $[1,3]$: 数据包为 $[2:2,3:3,4:4]$
$2:2$ 后面第一个优先级更高的是 $3:3$，输出 $3$
$3:3$ 后面第一个优先级更高的是 $4:4$，输出 $4$
$4:4$ 后面没有优先级更高的，不输出
输出: $3$ $4$

样例3

输入

4
3
4:4 3:3 2:2 1:1

输出

说明

窗口 $[0,2]$: 数据包为 $[4:4,3:3,2:2]$
$4:4$ 后面没有优先级更高的，不输出
$3:3$ 后面没有优先级更高的，不输出
$2:2$ 后面没有优先级更高的，不输出
该窗口不输出
窗口 $[1,3]$: 数据包为 $[3:3,2:2,1:1]$
$3:3$ 后面没有优先级更高的，不输出
$2:2$ 后面没有优先级更高的，不输出
$1:1$ 后面没有优先级更高的，不输出
该窗口不输出
所有窗口均无输出

样例4

输入

3
4
1:5 2:3 3:7

输出

说明

窗口大小 $4>$ 数据包数量 $3$，窗口无输出，无满足结果输出

题解

思路

思路：单调栈

1. 预处理:使用单调栈算法计算每个数据包右边第一个priority更高的数据包下标。具体逻辑为：

   1. 定义stk维持一个单调递减栈，栈中存储数据包下标。定义nextMaxIndex数组，存储每个位置右边第一个priority更高的数据包下标，开始所有值初始化为-1.
   2. 遍历输入数据包，遍历i时的处理逻辑：
      1. 递归维持栈递减，当栈非空，并且栈顶元素j小于当前数据优先级时，说明该位置为j右侧第一个大于它的下标，更新nextMaxIndex[j] = i,并弹出栈顶元素。
      2. 将i压入栈中，等待被处理。

2. 注意n < k时，直接返回为空即可。

3. 由于k <=100，可以枚举所有窗口，并求出每个窗口的结果序列，以这个{i, i + k -1}为例：

   1. 使用currentWindRes存储当前窗口结果。
   2. 确定窗口边界为windClose = i + k - 1
   3. 从前往后遍历{i, i + k -1}, 当前位置为j，如果nextMaxIndex[j] == -1 或者nextMaxIndex[j] > windClose 直接跳过(当前窗口内没有优先级更高)。否则加入{packets[j].id, packets[nextMaxIndex[j]].id}
   4. 按照3的逻辑处理之后，如果currentWindRes为空说明改窗口无输出，不添加进最终结果。

code

import java.util.*;

public class Main {

    public static List<List<Integer>> priorityPackets(int n, int k, List<int[]> packets) {
        List<List<Integer>> res = new ArrayList<>();

        if (n < k) return res;

        int[] nextMaxIndex = new int[n];
        Arrays.fill(nextMaxIndex, -1);

        Stack<Integer> stack = new Stack<>();

        // 单调栈：找下一个更大值
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() &&
                   packets.get(i)[1] > packets.get(stack.peek())[1]) {
                nextMaxIndex[stack.pop()] = i;
            }
            stack.push(i);
        }

        // 枚举窗口
        for (int i = 0; i <= n - k; i++) {
            int r = i + k - 1;
            List<Integer> cur = new ArrayList<>();

            for (int j = i; j <= r; j++) {
                if (nextMaxIndex[j] != -1 && nextMaxIndex[j] <= r) {
                    cur.add(packets.get(nextMaxIndex[j])[0]);
                }
            }

            if (!cur.isEmpty()) {
                res.add(cur);
            }
        }

        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.nextLine().trim());
        int k = Integer.parseInt(sc.nextLine().trim());

        String[] arr = sc.nextLine().trim().split(" ");

        List<int[]> packets = new ArrayList<>();

        for (String s : arr) {
            String[] tmp = s.split(":");
            packets.add(new int[]{
                Integer.parseInt(tmp[0]),
                Integer.parseInt(tmp[1])
            });
        }

        List<List<Integer>> res = priorityPackets(n, k, packets);

        if (res.isEmpty()) return;

        for (int i = 0; i < res.size(); i++) {
            if (i > 0) System.out.print(" ");
            for (int j = 0; j < res.get(i).size(); j++) {
                if (j > 0) System.out.print(",");
                System.out.print(res.get(i).get(j));
            }
        }
    }
}