public class MyStack {
int top;
Queue<Integer> q1;
Queue<Integer> q2;
public MyStack() {
q1=new LinkedList<Integer>();
q2=new LinkedList<Integer>();
}
public void push(int x) {
q2.offer(x);//offer是入队方法
while (!q1.isEmpty()){
q2.offer(q1.poll());//poll是出队方法
}
Queue<Integer> temp;
temp=q1;
q1=q2;
q2=temp;
}
public int pop() {
return q1.poll();
}
public int top() {
return q1.peek();//peek用于检索但不移除队列的头部元素
}
public boolean empty() {
return q1.isEmpty();
}
}
public class MyQueue {
Deque<Integer> inStack;
Deque<Integer> outStack;
public MyQueue() {
inStack=new ArrayDeque<Integer>();
outStack=new ArrayDeque<Integer>();
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
if(outStack.isEmpty()){
intooutStack();
}
return outStack.pop();
}
public int peek() {
if(outStack.isEmpty()){
intooutStack();
}
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty()&&outStack.isEmpty();
}
private void intooutStack(){
while (!inStack.isEmpty()){
outStack.push(inStack.pop());
}
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/构造函数 MyQueue(): 初始化了两个栈 inStack 和 outStack，分别用于入队和出队操作。
push(int x) 方法: 将元素 x 入队。直接将元素 x 压入 inStack 栈顶。
pop() 方法: 出队操作，返回队列的头部元素并将其移除。首先检查 outStack 是否为空，如果为空，则调用 intooutStack() 方法将 inStack 中的元素逐个弹出并压入 outStack，然后从 outStack 中弹出一个元素作为出队元素。
peek() 方法: 返回队列的头部元素，但不移除。同样，首先检查 outStack 是否为空，如果为空，则调用 intooutStack() 方法将 inStack 中的元素逐个弹出并压入 outStack，然后返回 outStack 栈顶元素。
empty() 方法: 检查队列是否为空。如果 inStack 和 outStack 都为空，则队列为空。
intooutStack() 方法: 将 inStack 中的元素逐个弹出并压入 outStack。这个方法在执行出队操作时会被调用，确保 outStack 中的元素顺序符合队列的先进先出特性。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
for (int i = 0; i < k; ++i) {
pq.offer(new int[]{nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = pq.peek()[0];
for (int i = k; i < n; ++i) {
pq.offer(new int[]{nums[i], i});
while (pq.peek()[1] <= i - k) {
pq.poll();
}
ans[i - k + 1] = pq.peek()[0];
}
return ans;
}
}
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
这段代码创建了一个优先队列 pq，其中存储了整数数组 int[]。在构造优先队列时，通过传入一个自定义的比较器 Comparator<int[]> 来指定元素的比较规则。
比较器中的 compare() 方法定义了元素的比较逻辑。在这个比较器中，首先比较两个元素的第一个元素 pair1[0] 和 pair2[0]，如果它们不相等，则按照元素的第一个值从大到小排序，即返回 pair2[0] - pair1[0]。如果第一个元素相等，则继续比较第二个元素 pair1[1] 和 pair2[1]，按照第二个元素从大到小排序，即返回 pair2[1] - pair1[1]。
这样定义的比较器保证了优先队列中的元素按照其第一个值从大到小排序，如果第一个值相等，则按照第二个值从大到小排序。这种排序方式可以确保优先队列中的头部元素始终是具有最大值的元素对 [nums[i], i]。
pq.offer(new int[]{nums[i], i});
ChatGPT
在这行代码中，pq.offer(new int[]{nums[i], i})，我们创建了一个整数数组 new int[]{nums[i], i}，其中 nums[i] 是当前元素的值，i 是当前元素的索引。然后，我们使用 pq.offer() 方法将这个数组作为一个元素添加到优先队列 pq 中。
这样，每个元素都以 [nums[i], i] 的形式存储在优先队列中，从而实现了按照元素值及其对应的索引进行排序。
对于这行代码 pq.peek()[1] <= i - k，它是在检查当前优先队列头部元素的索引是否小于等于 i - k，如果是，则表示该元素不在当前窗口内。让我来解释一下这行代码的作用：
pq.peek()：这会返回优先队列pq的头部元素，即具有最高优先级的元素，由于我们在构造优先队列时使用了自定义的比较器，头部元素是具有最大值的元素对[nums[i], i]。pq.peek()[1]：这会返回头部元素的索引部分，即i，这是因为我们将元素对[nums[i], i]存入优先队列中，第二个值是元素的索引。i - k：这表示当前窗口的左边界，即当前索引i减去窗口的大小k，这是为了确定当前窗口的范围。
所以，pq.peek()[1] <= i - k 的意思是，如果当前优先队列头部元素的索引小于等于当前窗口的左边界，即头部元素不在当前窗口内，那么我们需要将该元素从队列中弹出。
PriorityQueue 是 Java 中提供的一种优先队列的实现，它是一种特殊的队列，其中的元素被赋予了优先级。在 PriorityQueue 中，元素按照它们的自然顺序或者根据特定的 Comparator 接口进行排序。
- 当不提供自定义的比较器时，
PriorityQueue将使用元素的自然顺序进行排序。例如，如果队列存储的是整数，则队列将按照整数的大小进行排序，从小到大排列。 - 当提供了自定义的比较器时，
PriorityQueue将根据指定的比较规则对元素进行排序。
在这段代码中，我们使用了一个自定义的比较器，通过比较元素对 [nums[i], i] 中的第一个值（元素值）来进行排序。如果元素值不相等，则按照元素值从大到小排序；如果元素值相等，则按照第二个值（元素索引）从大到小排序。这样，优先队列中的头部元素始终是具有最大值的元素对 [nums[i], i]，从而实现了按照元素值及其对应的索引进行排序。
这段代码是标准的解法，它使用优先队列来解决滑动窗口最大值的问题。让我来逐步解释它的实现：
-
初始化：
- 创建了一个优先队列
pq，用于存储当前窗口内的元素，并按照元素值从大到小排序，如果元素值相等，则按照索引从大到小排序。 - 使用一个循环遍历数组
nums的前k个元素，将它们作为初始窗口，并加入优先队列pq中。
- 创建了一个优先队列
-
计算窗口最大值：
- 初始化一个长度为
n - k + 1的数组ans，用于存储每个窗口的最大值。 - 将第一个窗口的最大值（即优先队列的头部元素的值）存入
ans数组的第一个位置。 - 从第
k个元素开始遍历数组nums，并将每个元素加入到优先队列pq中。 - 对于每个窗口：
- 如果当前优先队列头部元素的索引小于等于
i - k，表示该元素不在当前窗口内，需要将其从队列中弹出。 - 将当前窗口的最大值存入
ans数组中。
- 如果当前优先队列头部元素的索引小于等于
- 初始化一个长度为
-
返回结果：
- 返回
ans数组，其中存储了每个窗口的最大值。
- 返回
这种实现方式利用了优先队列的特性，实现了对滑动窗口内的元素进行快速查找最大值的功能。
