滑动窗口

滑动窗口两个重要的操作

  1. 比较插入元素和窗口队尾元素的大小，如果插入元素比队尾元素更符合滑动窗口的性质，就删除队尾元素。
  2. 移动滑动窗口

我们要注意：使用单调队列实现滑动窗口。单调队列q[hh]中存放的是滑动窗口的最大元素的下标。

225. 用队列实现栈

思路

这道题我们使用java的LinkedList即可实现

如果需要使用queue来实现stack的操作，就需要两个队列

一个作为缓存队列q1，一个是真正存放元素的队列q2

pop：将q1除了队尾的元素，就放入q2中，然后返回q1的队尾元素。最后将q2中的元素再放入q1

push: q和stack的插入相同

top： 将q1除了队尾的元素，就放入q2中，然后返回q1的队尾元素t。将q2中的元素再放入q1，最后再把t放入q2中。

  1. class MyStack {
  3.     Deque<Integer> queue;
  4.     /** Initialize your data structure here. */
  5.     public MyStack() {
  6.         queue  = new LinkedList<Integer>();
  7.     }
  9.     /** Push element x onto stack. */
  10.     public void push(int x) {
  11.         queue.offerFirst(x);
  12.     }
  14.     /** Removes the element on top of the stack and returns that element. */
  15.     public int pop() {
  16.         return queue.pollFirst();
  18.     }
  20.     /** Get the top element. */
  21.     public int top() {
  22.         return queue.peek();
  23.     }
  25.     /** Returns whether the stack is empty. */
  26.     public boolean empty() {
  27.         return queue.isEmpty();
  28.     }
  29. }
  31. /**
  32.  * Your MyStack object will be instantiated and called as such:
  33.  * MyStack obj = new MyStack();
  34.  * obj.push(x);
  35.  * int param_2 = obj.pop();
  36.  * int param_3 = obj.top();
  37.  * boolean param_4 = obj.empty();
  38.  */

239. 滑动窗口最大值

标准滑动窗口

  1. class Solution {
  2.     public int[] maxSlidingWindow(int[] a, int k) {
  3.         //滑动窗口
  4.         int hh = 0, tt = -1;
  5.         int n = a.length;
  6.         if (n == 1) return a;
  7.         int[] q = new int[n];
  8.         ArrayList<Integer> res = new ArrayList<Integer>();
  9.         for (int i = 0; i < n; i ++){
  10.             if (hh <= tt && i - k + 1 > q[hh]) hh ++;
  11.             while( hh <= tt && a[i] > a[q[tt]]) tt--;
  12.             q[++ tt] = i;
  13.             if (hh <= tt && i - k + 1 >= 0) res.add(a[q[hh]]);
  14.         }
  15.         return res.stream().mapToInt(Integer::valueOf).toArray();
  16.     }
  17. }

剪枝offer版本

  1. class Solution {
  2.     public int[] maxInWindows(int[] nums, int k) {
  3.         //滑动窗口的两个重要操作：添加和移动
  4.         //移动：如果当前元素和窗口元素之差>窗口长度，窗口后移
  5.         // 添加：如果当前元素比窗口的末尾元素还要大，剔除末尾元素
  6.         int n = nums.length;
  7.         if (n <= 1) return nums;
  8.         int[] q = new int[n];
  9.         int[] res = new int[n - k + 1];
  10.         int hh = 0, tt = -1;
  11.         for (int i = 0; i <n; i ++){
  12.             //移动
  13.             while (hh <= tt && i - q[hh] + 1 > k) hh++;
  14.             //添加
  15.             while (hh <= tt && nums[i] > nums[q[tt]]) tt--;
  16.             q[++tt] = i;
  17.             //输出
  18.             if (i >= k - 1) res[i - k + 1] = nums[q[hh]];
  19.         }
  20.         return res;
  21.     }
  22. }

单调队列优化 64. 字符流中第一个只出现一次的字符

维护一个HashMap（存放每个字符出现的次数）

再维护一个队列(答案满足先进先出的原则)，顺序存放第一个出现一次的字符。

每次加入字符的时候,插入HashMap中，HashMap判断：如果队列头部的字符在HashMap中出现了两次，队列pop。

这样最终指针的元素就是第一个只出现一次的字符。

插入操作：插入HashMap， o(1)

更新队列操作： 指针一共只遍历n次 o(n)

计算p[]为前缀和

那么p[j] - p[i] >= k就代表区间[i, j]和至少为k

此时j - i就是区间的长度

维护一个新的滑动窗口，具体做法是：

q[]存放满足性质的p中元素的下标，此窗口满足递增的性质， 这样p[j] - p[q[hh]]尽可能大

当遍历元素a[j] <= a[q[tt]] tt—

当p[j] - p[q[hh]] >= k，就移除队首元素i，并且计算答案（i - q[hh]），因为 j - i如果满足， 由于窗口是递增的， j后面的元素也满足，但是区间不是最短的

debug了一个小时，结果发现前缀和求错了。。

  1. class Solution {
  2.     public int shortestSubarray(int[] a, int K) {
  3.         //和至少为k的最短长度
  4.         //分别从1~n递增滑动窗口的长度，如果达到k，就返回k
  5.         int n = a.length;
  6.         long[] prefix = new long[n + 1];
  7.         for (int i = 1; i <= n; i ++){
  8.             prefix[i] = (long)a[i - 1] + prefix[i - 1];
  9.             //System.out.print(prefix[i] + " ");
  10.         }
  12.         int q[] = new int[n + 1];
  13.         int hh = 0, tt  = -1;
  14.         int res = n + 1;
  15.         for (int i = 0; i <= n; i ++){
  17.             while (hh <= tt && prefix[i] < prefix[q[tt]]) tt--;
  18.             while (hh <= tt && prefix[i] - prefix[q[hh]] >= K){
  19.                 res = Math.min(res, i - q[hh]);
  20.                 hh ++;
  21.             }
  22.             q[++ tt] = i;
  23.         }
  24.         return res <= n ? res : -1;
  25.     }
  26. }

II. 队列的最大值 - 力扣（LeetCode） (leetcode-cn.com)

和之前的求栈的最小值的思路正好相反

求栈的最小值中，由于ArrayList 和 Stack添加删除元素的顺序是一样的，因此构造了单调递增的ArrayList

因此这道题不能使用ArrayList，要构造单调递减的Deque，队尾元素就是最大值。


class MaxQueue {
    //定义一个单调递减的queue，每次插入都存放queue中，
    //每次pop取出最后一个值，判断value是否和queue的堆首（最大的元素相等），如果相等，两个队列都pop，不相等，原队列pop
    //注意，显示最大元素的时候，需要判断原队列是否为空，如果原队列为空，就不能再判断
    Deque<Integer> cache;
    Queue<Integer> q;
    public MaxQueue() {
        cache = new LinkedList<Integer>();
        q = new LinkedList<Integer>();
    }

    public int max_value() {
        if (q.isEmpty()) return -1;
        return cache.getLast();
    }

    //构造递减序列
    public void push_back(int value) {
        while (!cache.isEmpty() && value > cache.getFirst()) cache.pollFirst();
        cache.addFirst(value);
        q.add(value);
    }

    public int pop_front() {
        if (q.isEmpty()) return -1;
        int t = q.peek();
        if (t == cache.getLast())
            cache.pollLast();
        return q.poll();
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */