网站开发赚钱吗 知乎,wordpress首页调用指定文章,erp123登录入口,山东省住房和城乡建设厅地址洛谷 P2032 扫描 (Java)
传送门#xff1a;P2032 扫描
题目#xff1a; 扫描
题目描述
有一个 1 n 1 \times n 1n 的矩阵#xff0c;有 n n n 个整数。
现在给你一个可以盖住连续 k k k 个数的木板。
一开始木板盖住了矩阵的第 1 ∼ k 1 \sim k 1∼k 个数#x…洛谷 P2032 扫描 (Java)
传送门P2032 扫描
题目 扫描
题目描述
有一个 1 × n 1 \times n 1×n 的矩阵有 n n n 个整数。
现在给你一个可以盖住连续 k k k 个数的木板。
一开始木板盖住了矩阵的第 1 ∼ k 1 \sim k 1∼k 个数每次将木板向右移动一个单位直到右端与第 n n n 个数重合。
每次移动前输出被覆盖住的数字中最大的数是多少。
输入格式
第一行两个整数 n , k n,k n,k表示共有 n n n 个数木板可以盖住 k k k 个数。
第二行 n n n 个整数表示矩阵中的元素。
输出格式
共 n − k 1 n - k 1 n−k1 行每行一个整数。
第 i i i 行表示第 i ∼ i k − 1 i \sim i k - 1 i∼ik−1 个数中最大值是多少。
样例 #1
样例输入 #1
5 3
1 5 3 4 2样例输出 #1
5
5
4提示
对于 20 % 20\% 20% 的数据 1 ≤ k ≤ n ≤ 1 0 3 1 \leq k \leq n \leq 10^3 1≤k≤n≤103。
对于 50 % 50\% 50% 的数据 1 ≤ k ≤ n ≤ 1 0 4 1 \leq k \leq n \leq 10^4 1≤k≤n≤104。
对于 100 % 100\% 100% 的数据 1 ≤ k ≤ n ≤ 2 × 1 0 6 1 \leq k \leq n \leq 2 \times 10^6 1≤k≤n≤2×106矩阵中的元素大小不超过 1 0 4 10^4 104 并且均为正整数。
分析
这道题可以用单调队列来解决。
单调队列是一种数据结构它保证队列中元素的顺序单调递增或递减。
单调队列可以用于解决很多与滑动窗口相关的题目例如
最大子序和最小滑动窗口最长递增子序列
这道题可以用单调队列来维护一个最大值队列用于找出每次移动木板时被覆盖的数字中的最大值。
算法的核心思想是使用一个双端队列来存储当前被覆盖数字的下标并保证队列中的数字是单调递减的。这样在每次移动木板时队列的第一个元素即为当前被覆盖数字中的最大值。
实现方法
初始化双端队列 b 和队头 hh、队尾 ttb 用于存储当前被覆盖数字的下标hh 和 tt 分别表示队列的队头和队尾。
执行扫描算法使用循环遍历矩阵中的每个元素从下标 0 到 n-1。
向右移动木板如果队列中的数字个数大于 0且当前的下标与队头元素相差超过了 k则将队头元素出队即向右移动木板。
保证队列单调递减在每次遍历元素时如果队列中有元素并且当前元素大于等于队列末尾元素对应的数字则将队尾元素出队直到队列中的元素单调递减。
将当前下标加入队列并更新队尾指针 tt。
如果当前下标大于等于 k-1则输出队头元素对应的数字即当前被覆盖数字中的最大值。
该算法的时间复杂度为 O(n)因为每个元素最多入队和出队一次。
代码
import java.util.ArrayList;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int k sc.nextInt();ArrayListInteger a new ArrayList();ArrayListInteger b new ArrayList();for(int i 0;i n;i) {a.add(sc.nextInt());}sc.close();// hh表示对头tt表示队尾int hh 0;int tt 0;for(int i 0;i n;i) {// 向右移动if(tt-hh0b.get(hh)ki) {hh;}// 保证单调递减while(tt-hh0a.get(i)a.get(b.get(tt-1))) {b.remove(tt-1);tt--;}tt;b.add(i);if(ik-1)System.out.println(a.get(b.get(hh)));}}
}
