剑指 Offer 59 - I. 滑动窗口的最大值
题目说明
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
解题思路
本题的关键在于，后来的值是会对之前来的值造成影响的。具体的说就是，如果序列是[1, 2, 3]，此时如果插入4，前面值之前记录的最大值都变成了4，之前维护的最大值也就没有意义了，可以舍弃。如果接下来又来了个3，依然不会对4及4前面的那些值造成影响，但是如果4出去之后最大值就不再是4了，因此要记录下来。
因此我们可以看出，我们需要维护的是一个单调递减的序列。且如果当队头就是最大值时，队列出队时辅助队列也需要poll。此外，如果当辅助队列的队尾和新来的值一样大时，也同样需要入队。因此我们需要对辅助队列的队尾队首都操作，我们需要一个双端队列。
此时还可以用一个技巧。因为同时需要对结果数组和给定数组进行定位，分别用 i 和 j 。实际上结尾数组相当于是从给定数组位置到达k时才开始计算，因此我们可以将i初始化为1 - k。当 i > 0之后，则用i - 1去和 deque.peek() 比较进行更新即可（出窗口的数字需要出队）
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
Deque<Integer> deque = new LinkedList<Integer>();
// i定位res, j定位nums
for (int j = 0, i = 1 - k; j < nums.length; j++, i++) {
// 针对出窗口元素进行处理
if (i > 0 && nums[i - 1] == deque.peekFirst()) {
deque.pollFirst();
}
// 入窗口，维护辅助队列单调性
while (!deque.isEmpty() && deque.peekLast() < nums[j]) {
deque.pollLast();
}
deque.offerLast(nums[j]);
// 获得结果
if(i >= 0) {
res[i] = deque.peekFirst();
}
}
return res;
}
}
剑指 Offer 59 - II. 队列的最大值
题目说明
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
解题思路
和前一题基本的逻辑是相似的，同样是需要维护一个单调递减的辅助队列
区别在于出队的条件变了。之前是固定窗口大小，窗口内数字的数量是一定的。现在则是根据出队操作来触发
关于Queue和List
Queue
在 Java 中，我们可以使用 Queue 接口和它的实现类（如 LinkedList 或 PriorityQueue）来创建队列。插入操作通过 add() 或 offer() 方法进行，删除操作通过 remove() 或 poll() 方法进行。
add、offer、remove 和 poll 都用于元素的添加和删除。然而，他们在操作失败时的行为是有所不同的
add和remove在操作失败时（如队列已满，队列为空）会抛出一个异常，offer失败时返回false，poll失败时会返回null。在实际情况中可以根据具体的需求来决定使用哪一种方法；
双端队列（Double Ended Queue）
Java 的 Deque 接口和它的实现类（如 ArrayDeque 和 LinkedList）提供了双端队列的功能。
添加元素
addFirst(E e): 将指定元素插入此双端队列的开头。addLast(E e): 将指定元素插入此双端队列的末尾。offerFirst(E e): 在此双端队列的开头插入指定的元素。offerLast(E e): 在此双端队列的末尾插入指定的元素。
删除元素
removeFirst(): 获取并移除此双端队列的第一个元素。removeLast(): 获取并移除此双端队列的最后一个元素。pollFirst(): 获取并移除此双端队列的第一个元素，若此双端队列为空，则返回 null。pollLast(): 获取并移除此双端队列的最后一个元素，若此双端队列为空，则返回 null。
检索元素
getFirst(): 获取但不移除此双端队列的第一个元素。getLast(): 获取但不移除此双端队列的最后一个元素。peekFirst(): 获取但不移除此双端队列的第一个元素，若此双端队列为空，则返回 null。peekLast(): 获取但不移除此双端队列的最后一个元素，若此双端队列为空，则返回 null。
LinkedList 和 ArrayList
-
ArrayList 是基于动态数组实现的，所以它在随机访问（通过索引查找）时非常快，时间复杂度为 O(1)。然而，由于需要大块连续的内存空间，当插入和删除元素时，可能需要移动其他元素以保持数组的连续，这使得其在插入和删除元素上的性能较差，尤其是在列表的中间或开头进行操作时，时间复杂度为 O(n)。
-
LinkedList 是基于双向链表实现的，所以它在元素的插入和删除（尤其是在列表的开头和结尾）上很快，时间复杂度为 O(1)。然而，由于需要遍历链表来查找元素，所以它在随机访问时的性能较差，时间复杂度为 O(n)。
因此，如果需要执行大量的随机访问操作，ArrayList 可能是更好的选择。如果你主要需要执行大量的插入和删除操作，那么 LinkedList 可能会更好。在实现队列时，由于队列主要在一端（队尾）添加元素，并从另一端（队头）删除元素，所以 LinkedList 通常是更好的选择。
优先队列（Priority Queue）
Java 的 PriorityQueue 类就是一个优先队列的实现。这个队列会根据元素的自然顺序或者比较器（Comparator）来决定出队顺序。
优先队列操作的具体方法和Queue是相同的
主要特性：
-
元素排序：
PriorityQueue中的元素默认会按照自然顺序（即数字从小到大、字母从 A 到 Z）进行排序。也就是说，默认情况下，优先级最小的元素最先出队。我们也可以通过提供一个Comparator对象来自定义元素的排序规则。 -
非线程安全：
PriorityQueue不是线程安全的。如果需要在多线程环境中使用优先队列，可以考虑使用PriorityBlockingQueue。
自定义比较器：
// 创建一个优先队列，然后按照字符串长度的升序进行排序
PriorityQueue<String> queue = new PriorityQueue<>(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s1.length() - s2.length();
}
});
PriorityQueue<String> queue = new PriorityQueue<>((s1, s2) -> s1.length() - s2.length());
关于线程安全
"线程安全"是多线程编程中的术语，如果代码是线程安全的，那么它在同时被多个线程访问时，其行为仍然是正确的。这意味着无论操作系统如何切换执行线程，结果都是预期的，不会出现数据竞争或者其他意料之外的结果。
而"非线程安全" 则是指在多线程环境下，一个对象的方法可能会受到其他线程方法的干扰，不能保证数据的完整性和一致性。结果可能取决于线程的调度顺序，这通常是我们不希望发生的。
举个例子，假设有两个线程同时对一个优先队列进行插入操作，由于 PriorityQueue 是非线程安全的，所以可能会出现问题。一个可能的情况是一个线程已经开始了插入操作，但在完成之前，操作系统切换到另一个线程，另一个线程也尝试插入元素。结果可能会导致队列中的某些元素状态不正确。
在处理这种情况的一种常见手法是使用锁来同步对共享资源的访问。Java提供了多种机制，例如synchronized关键字或者显式锁（java.util.concurrent.locks.Lock），可以用来同步对共享资源的访问，从而确保线程安全。
当然，如果你只在单线程环境下使用PriorityQueue，那么就不存在线程安全问题。