蓝桥杯练习题（九）

📑前言

本文主要是【算法】——蓝桥杯练习题（九）的文章，如果有什么需要改进的地方还请大佬指出⛺️

🎬作者简介：大家好，我是听风与他🥇
☁️博客首页：CSDN主页听风与他
🌄每日一句：狠狠沉淀，顶峰相见

1142.百亿富翁

package 蓝桥杯第九次;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class 百亿富翁 {
/*
5
3 1 2 5 4
 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		sc.nextToken();
		int n = (int)sc.nval;
		long a[] = new long[n+1];
		for(int i=1;i<=n;i++) {
			sc.nextToken();
			a[i]=(long)sc.nval;
		}
		int num1[] = new int[n+1];
		int num2[] = new int[n+1];
		Arrays.fill(num1, -1);
		Arrays.fill(num2, -1);
		Deque<Integer> q = new ArrayDeque<>();
		//按顺序遍历
		for(int i=1;i<=n;i++) {
			while(!q.isEmpty()&&a[q.peekLast()]<a[i]) q.pollLast();
			if(!q.isEmpty()) {
				num1[i]=q.peekLast();
			}
			q.add(i);
		}
		q.clear();
		//倒过来遍历就是右边第一栋比自己高
		for(int i=n;i>=1;i--) {
			while(!q.isEmpty()&&a[q.peekLast()]<a[i]) q.pollLast();
			if(!q.isEmpty()) {
				num2[i]=q.peekLast();
			}
			q.add(i);
		}
		for(int i=1;i<=n;i++) {
			System.out.print(num1[i]+" ");
		}
		System.out.println();
		for(int i=1;i<=n;i++) {
			System.out.print(num2[i]+" ");
		}
	}

}

1207.MAX最值差

package 蓝桥杯第九次;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayDeque;
import java.util.Deque;

public class MAX最值差 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		sc.nextToken();
		int n = (int)sc.nval;
		sc.nextToken();
		int k= (int)sc.nval;
		int a[] = new int[n+1];
		for(int i=1;i<=n;i++) {
			sc.nextToken();
			a[i] = (int)sc.nval;
		}
		Deque<Integer> q = new ArrayDeque<>();
		int num1[] = new int[n+1];
		int num2[] = new int[n+1];
		for(int i=1;i<=n;i++) {
			while(!q.isEmpty()&&i-k>=q.peekFirst()) q.pollFirst();
			while(!q.isEmpty()&&a[i]<a[q.peekLast()]) q.pollLast();
			q.addLast(i);
			num1[i]=q.peekFirst();
		}
		q.clear();
		for(int i=1;i<=n;i++) {
			while(!q.isEmpty()&&i-k>=q.peekFirst()) q.pollFirst();
			while(!q.isEmpty()&&a[i]>a[q.peekLast()]) q.pollLast();
			q.addLast(i);
			num2[i]=q.peekFirst();
		}
		int max = Integer.MIN_VALUE;
		for(int i=1;i<=n;i++) {
			max = Math.max(a[num2[i]]-a[num1[i]], max);
		}
		System.out.println(max);
	}
/*
6 3 
4 6 5 2 3 1
 */
}

2219.左移右移

package 蓝桥杯第九次;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class 左移右移2 {

	static class Node{
		int val;;
		Node pre;
		Node next;
		public Node(int val,Node pre,Node next) {
			this.val = val;
			this.pre = pre;
			this.next = next;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		Map<Integer, Node> map = new HashMap<>();
		Node head = new Node(-1, null, null);
		Node tail = new Node(-1, null, null);
		Node pre = head;
		for(int i=1;i<=n;i++) {
			pre.next = new Node(i, pre, null);
			pre = pre.next;
			map.put(i, pre);
		}
		pre.next = tail;
		tail.pre = pre;
		while(m-->0) {
			char c = sc.next().charAt(0);
			int k = sc.nextInt();
			Node node = map.get(k);
			node.next.pre = node.pre;
			node.pre.next = node.next;
			if(c=='L') {
				head.next.pre = node;
				node.next = head.next;
				head.next = node;
				node.pre = head;
			}else {
				node.pre = tail.pre;
				tail.pre.next = node;
				node.next = tail;
				tail.pre = node;
			}
		}
		Node cur = head.next;
		while(cur!=tail) {
			System.out.print(cur.val+" ");
			cur = cur.next;
		}
	}

}