会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
枚举窗口最小值朴素解法
这道题的正解是 单调队列，但是我们用朴素解法 每段暴力求窗口最小值 也能在考试时拿到一定的分数。
题意：第 i 号路段（路口 i 与 i+1 之间）可连接的基站编号区间为
L=max(0,i+1−k),R=min(N−1,i+k)
在该区间内选接入人数最少的基站编号；人数相同时取靠右的编号。非法输入输出 −1。
题目内容
某闹市街道沿线设有 N 个路口，编号依次为 0 到 N−1。每个路口建有一座通信基站，第 i 号路口基站的当前接入人数记为 crossroads[i]。对于编号为 j 的基站，其信号覆盖前后各 k 个路口，即覆盖路口编号区间 [j−k,j+k]。
小明从 0 号路口出发，沿街道向前走到 N−1 号路口。将 i 号路口到 i+1 号路口之间的道路称为第 i 个路段，其中 0≤i≤N−2。当小明位于某个路段时，可能有多个基站的覆盖范围包含该路段。手机将从这些基站中选择当前接入人数最少的一个建立通信。如果有多个并列最少的基站，则选择编号最大的基站。
对于第 i 个路段，覆盖该路段的基站编号 j 需要满足：
max(0,i+1−k)≤j≤min(N−1,i+k).
请计算小明沿途经过的每一个路段所对应的最佳基站编号。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
