李某人的编程宝库

# 算法

# 优先队列

# 优先队列的使用

优先队列，也称为堆，是一种特殊的队列数据结构，能够始终保持队列中的元素有序。其底层实现通常为一颗完全二叉树。根据排序规则的不同，优先队列分为两种类型：

  • 小根堆：堆顶元素为队列中的最小值，出队时元素按升序排列
  • 大根堆：堆顶元素为队列中的最大值，出队时，元素按降序排列

image-20241130094235687

# 优先队列定义方式如下:

Queue<Integer> q = new PriorityQueue<>();
Queue<Integer> q = new PriorityQueue<>((x,y)->y-x);
1
2

常见操作:

image-20241130094351132

# 遍历优先队列

Queue<Integer> q = new PriorityQueue<>();
while(!q.isEmpty()){
    out.println(q.poll());
}
1
2
3
4

时间复杂度为O(n log n)

# 例题:堆排序

https://www.lanqiao.cn/problems/4333/learning/?page=1&first_category_id=1&name=%E5%A0%86%E6%8E%92%E5%BA%8F

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

/**
 * @ Author: 李某人
 * @ Date: 2024/11/30/9:48
 * @ Description: https://www.lanqiao.cn/problems/4333/learning/?page=1&first_category_id=1&name=%E5%A0%86%E6%8E%92%E5%BA%8F
 */
public class Main {

    static Queue<Integer> queue = new PriorityQueue<>();
    public static void main(String[] args) {
        /**
         * push：将一个正整数 x 插入堆中。
         * remove：删除堆顶元素。若此时堆为空，则输出 empty。
         * min：输出堆中最小的元素。若此时堆为空，则输出 empty。
         * print：给定一个小于等于当前堆中元素的数字 k，你需要在一行内输出当前堆中最小的 k 个元素，并将其全部删除，数据保证该操作不会在堆为空时出现。
         */
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//第一行
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            if (s.equals("push")){
                int x = sc.nextInt();
                push(x);
            }else if (s.equals("remove")){
                remove();
            }else if (s.equals("min")){
                min();
            }else if (s.equals("print")){
                int k = sc.nextInt();
                print(k);
            }
        }

    }
    public static void push(int x){
        queue.offer(x);
    }
    public static void remove(){
        if (queue.isEmpty()) {
            System.out.println("empty");
        }else {
            queue.poll();
        }
    }
    public static void min(){
        if (queue.isEmpty()) {
            System.out.println("empty");
        }else {
            System.out.println(queue.peek());
        }
    }
    //print：给定一个小于等于当前堆中元素的数字 k，你需要在一行内输出当前堆中最小的 k 个元素，并将其全部删除，数据保证该操作不会在堆为空时出现。
    public static void print(int k){
        for (int i= 1 ; i<=k; i++){
            System.out.println(queue.poll());
        }
        System.out.println();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

# 单调栈

我们先来看一个数据的左右最值问题

题目要求：

给定一个长度为N的序列a。

输出每个数字其左边第一个比其大的数字，不存在则输出-1

考虑暴力做法，枚举每个数字到其最左边，找到最大的数，时间复杂度为O(n2)。

// 方法一：暴力解法 O(n²)
    public static int[] findLeftLarger1(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];

        for (int i = 0; i < n; i++) {
            result[i] = -1;  // 默认为-1
            // 向左遍历寻找第一个更大的数
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > arr[i]) {
                    result[i] = arr[j];
                    break;
                }
            }
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

建议使用单调栈解法，因为：

时间复杂度更优（O(n) vs O(n²)）

代码更简洁高效

适用于处理大规模数据

image-20241203112848263

# 针对本题的操作

答案的条件：在左边、最近的、比他大的数。

用单调栈来维护一个下标序列，使得栈中下标所代表的元素保持单调递减的顺序，即栈顶最小，栈底最大。

每次遍历到一个元素，判断完之后将他的下标压入占中。

则单调栈天然满足：栈顶元素离他最近。

我们只需要判断是否栈顶元素比他大即可，如果栈顶元素比他大，那么栈顶元素就是他左边第一个比他大的数

反之，如果栈顶元素比他小，那么弹出栈顶元素，直到栈顶元素比他大为止，或者栈为空

# 例题:单调栈

https://www.lanqiao.cn/problems/19871/learning/?page=1&first_category_id=1&tags=%E5%8D%95%E8%B0%83%E6%A0%88&tag_relation=intersection&sort=pass_rate&asc=0

import java.util.*;

public class Main {
    // 查找左边第一个更大的数
    public static int[] findLeftLarger(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : arr[stack.peek()];
            stack.push(i);
        }
        return result;
    }
    
    // 查找右边第一个更大的数
    public static int[] findRightLarger(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : arr[stack.peek()];
            stack.push(i);
        }
        return result;
    }
    
    // 查找左边第一个更小的数
    public static int[] findLeftSmaller(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : arr[stack.peek()];
            stack.push(i);
        }
        return result;
    }
    
    // 查找右边第一个更小的数
    public static int[] findRightSmaller(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : arr[stack.peek()];
            stack.push(i);
        }
        return result;
    }
    
    // 打印数组
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(" ");
            }
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        // 读入数组
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        // 计算并输出结果
        printArray(findLeftLarger(arr));    // 左边第一个更大的数
        printArray(findRightLarger(arr));   // 右边第一个更大的数
        printArray(findLeftSmaller(arr));   // 左边第一个更小的数
        printArray(findRightSmaller(arr));  // 右边第一个更小的数
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

# 单调队列

单调队列(Monotonic Queue)是一种特殊的队列，它维护队列中的元素按某种顺序排列，通常用于在滑动窗口问题中保持窗口的最大值或最小值

根据不同的需求，单调队列可以分为：

  • 单调递减队列：队列中的元素从前到后递减，这样队列的首元素始终是当前窗口的最大值
  • 单调递增队列：队列中的元素从前到后递增，这样队列的首元素始终是当前窗口的最小值

单调队列解决该问题时间复杂度为O(n)

1.**维护单调性:**队列中的元素始终保持单调递增或递减。对于求最小值的情况，队列应保持单调递增(队头最小):对于求最大值的情况，队列应保持单调递减(队头最大)

2.窗口内元素的更新:

队列中的每个元素代表当前窗口中的候选值(对应下标).

如果一个元素在队列尾部比新加入的元素大或者相等，则说明它不可能称为后续窗口的最小值(或最大值)，因此看也将其移出

每次加入新元素时，通过比较并维护队列的单调性

3.移出过期元素:

队列头部存储的是当前滑动窗口内最优价值的元素，当队列中的元素超出滑动窗口时，将其移出。

假设有一个数组 a[] = [2,1,3,4,6,3,8,5,7]和一个窗口大小 k = 3，我们需要输出每个滑动窗口的最小值

1.第一个窗口([2,1,3]):最小值是1

# 单调队列的实现

[2,1,3,4,6,3,8,5,7]

1.第一步：

元素a[0] = 2 窗口[2]

  • 队列为空，直接加入当前元素的下标0,deque = [0]
  • 当前窗口大小不够，不能输出

2.第二步:

元素a[1] = 1 窗口[2,1]

  • 队列中的a[0] = 2 大于 a[1] = 1，保持队列不变，直接加入下标1，deque = [0,1]
  • 当前窗口大小不够，不能输出

3.第三步:

元素a[2] = 3 窗口[2,1,3]

  • 队列中的a[1] = 1 小于a[2] = 3，将下标1移出队列
  • 队列中的a[0] = 2 小于 a[2] = 3 ，将下标0 移出队列
  • 加入下标2，deque = [2]
  • 当前窗口[2,1,3]的最大值为a[2] = 3

4.第四步:

元素 a[3]= 4，窗口 [1,3,4]

队列中的 a[2]=3小于 a[3]=4，将下标2移出队列。

加入下标 3，deque = [3]。

当前窗口[1,3,4]的最大值为 a[3]= 4。

5.第5步:

  • 元素 a[4]=6，窗口 [3,4,6]
  • 队列中的 a[3]=4小于 a[4]=6，将下标3移出队列。
  • 加入下标4，deque = [4]。
  • 当前窗口 [3,4,6] 的最大值为 a[4]= 6。

6.第六步:

  • 元素 a[5]= 3，窗口 [4,6,3]
  • 队列中的 a[4]=6大于 a[5]= 3，保持队列不变。
  • 加入下标 5，deque =[4，5]。
  • 当前窗口 [4,6,3]的最大值为 a[4]=6。
完善页面 (opens new window)
最近更新: 5/20/2025, 2:44:56 PM
算法
失败才是人生的主旋律   |