蓝桥杯算法心得——附近最小（优先队列+滑动窗口）

本文主要是介绍蓝桥杯算法心得——附近最小（优先队列+滑动窗口），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大家好，我是晴天学长，这题可以用贪心优先队列和滑动窗口来写，需要的小伙伴可以关注支持一下哦！后续会继续更新的。💪💪💪

1) .附近最小

在这里插入图片描述
问题描述
小蓝有—个序列a[1], a[2],...,a[n]。
给定—个正整数k，请问对于每一个1到n之间的序号i，a[i- k], a[i-k ＋1],..., ai＋剐]这2k ＋1个数中的最小值是多少?
当某个下标超过1到n的范围时，数不存在，求最小值时只取存在的那些值。
输入格式
输入的第一行包含一整数n。
第二行包含n个整数，分别表示a[1], a[2],..., a[n]。
第三行包含一个整数k。
输出格式
输出一行，包含n个整数，分别表示对于每个序号求得的最小值。
样例输入
5
5 27 4 3
样例输出
2 2 2 3 3

2) .算法思路

附近最小
用滑动窗口和优先队列写
1.用队列
1.接收数据
2.优先队列
int【】第一个存大小，第二个存位置
3.先存数据进去

开始遍历
1.优先队列都要压进去
2.前进（3种）
1.最小值过了
2.更新最小值
3.最小值不变

3）.算法步骤

4）. 代码实例

package LanQiaoTest;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;public class 附近最小 {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static String[] strings;public static void main(String[] args) throws IOException {strings = in.readLine().split(" ");int n = Integer.parseInt(strings[0]);int[] N = new int [n];strings = in.readLine().split(" ");for (int i = 0; i < N.length; i++) {N[i] = Integer.parseInt(strings[i]);}strings = in.readLine().split(" ");int k = Integer.parseInt(strings[0]);PriorityQueue<int[]> queue = new PriorityQueue<>((o1,o2)->(o1[0]-o2[0]));for (int i = 0; i <= k; i++) {queue.add(new int[] {N[i],i});}int[] result = new int[n];for (int i = 0; i < result.length; i++) {if(!(i>=n-k)) {queue.add(new int[] {N[i+k],i+k});}while (!queue.isEmpty()&&queue.peek()[1]<i-k) {queue.poll();}result[i] = queue.peek()[0];}for (int i = 0; i < result.length; i++) {System.out.print(result[i]+" ");}}}