道路最佳通信基站

题目描述

给定长度为 N 的数组 crossroads[]，其中 crossroads[i] 表示第 i 号路口基站的当前接入人数；以及覆盖范围 k。
基站 i 可覆盖路口 [max(0, i−k) … min(N−1, i+k)]。
小明从 0 号路口出发，走过第 i 段路（路口 i 到 i+1 之间）时，可连接所有覆盖该路段的基站，需选择接入人数最少的基站。
返回长度为 N−1 的数组 ret，其中 ret[i] 为第 i 段路的最佳基站编号。

解题思路

题目内容

闹市区中有一条马路，马路从$0$号路口开始，到$N-1$号路口结束，在每个路口都架设了最新技术的通信基站，每个基站的信号可以覆盖前后各$k$个路口的范围，即第1个路口上的基站，可以覆盖$[i-k,i+k]$这两个路口之间的马路，因此用户的手机处于多个基站的覆盖范围中。每个基站会统计当前接入人数，为保障最佳通信质量，用户手机应选择连接人数最少的基站进行通讯。

这条马路一共$N$个路口，小明从$0$号路口出发向前走，求小明在每个路段中的最佳通讯基站。不考虑处于路口中间的特殊场景,只考虑在每个路段中的场景，例如第1个路段应为$0$号路口到$1$号路口之间的路段，如果基站覆盖范围$k=2$，此时最佳基站应为$0、1、2$中连接人数最少的基站。

输入描述

输入为两行

第一行长度为$N$的整数数组$crossroads[]$，数组元素以空格分隔，其中$crossroads[i]$表示$i$号路口基站的当前接入人数。

$1<=crossroads.length$数组长度$<=10^5，0<=crossroads[i]<=10^2$

第二行为基站覆盖范围$k$，$1 <= k <= crossroads.length$

非法输入返回$-1$

输出描述

返回一个数组$ret，ret[i]$表示$i$路段上最佳基站的编号，数组元素之间以空格分隔。例如$0$号路口到$1$号路口的路段，为$0$号路段，其最佳基站用$ret[0]$表示。

样例1

输入

3 5 8 7 6 7 4
2

输出

0 0 1 4 6 6 

说明

小明在第$1$段路时，位于$0$号和$1$号基站中间，此时可以连接到$0、1、2$这$3$个基站，而这三个基站中连接数最小的是$0$号基站($3$个人)，因此输出数组第一个元素应为$0$号基站。小明位于第$2$段路时，位于$1$号和$2$号基站中间，此时可以连接到$0、1、2、3$这$4$个基站，选择其中连接人数最小的基站，即$0$号基站($3$人)，因此输出数组第二个元素为$0$号基站。以此类推。

样例2

输入

9 8 7 6 7 8 9
2

输出

2 3 3 3 3 4

说明

小明在第$1$段路时，可以连接到的基站为$0、1、2$这$3$个基站，其中连接人数最小的基站为$2$号基站($7$人连接)，因此输出数组第一个元素为$2$号基站。以此类推。