sliding window maximum

• cf sliding window median: using two heaps
• use deque
  • main idea: only keep promising candidates and maintain related index order
  • when enqueue, popLast() all numbers that are smaller than coming element, addLast() new elements
  • when dequeue, when the element exist, popFirst()
  • get result: add peekFirst()

public class Solution {
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
        // write your code here
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        ArrayList<Integer> rst = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            inQueue(nums[i], deque);
            if (i - k >= 0) {
                outQueue(nums[i-k], deque);
            }
            if (i + 1 - k >= 0) {
                rst.add(deque.peekFirst());
            }
        }
        return rst;
    }

    private void inQueue(int num, ArrayDeque<Integer> deque) {
        while (!deque.isEmpty() && num > deque.peekLast()) {
            deque.pollLast();
        }
        deque.addLast(num);
    }

    private void outQueue(int num, ArrayDeque<Integer> deque) {
        if (deque.peekFirst() == num) {
            deque.pollFirst();
        }
    }
};

sliding window median

• two heaps

public class Solution {
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((v1,v2) -> v2.compareTo(v1)); // v2-v1 will exceed limit

    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length - k + 1;
        if (n <= 0) return new double[0];
        double[] result = new double[n];

        for (int i = 0; i < nums.length; i++) {
            add(nums[i]);
            if (i >= k) remove(nums[i-k]);
            if (i + 1 >= k) result[i+1-k] = getMedian();            
        }

        return result;
    }

    private void add(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());

        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    private void remove(int num) {
        if (maxHeap.contains(num)) {
            maxHeap.remove(num);
        }
        else {
            minHeap.remove(num);        
        }

        if (minHeap.size() > maxHeap.size()) {  // when remove from maxHeap, maxHeap may have one less elements
            maxHeap.offer(minHeap.poll());
        }

        if (maxHeap.size() - minHeap.size() > 1) {  // when remove from minHeap, maxHeap may have two more elements
            minHeap.offer(maxHeap.poll());
        }
    }

    private double getMedian() {
        if (maxHeap.isEmpty() && minHeap.isEmpty()) return 0;

        if (maxHeap.size() == minHeap.size()) {
            return ((double)maxHeap.peek() + (double)minHeap.peek()) / 2.0;
        }
        else {
            return (double)maxHeap.peek();
        }
    }
}

sliding window moving average (Moving Average from Data Stream)

• one queue

public class MovingAverage {
    /*
    * @param size: An integer
    */

    int size;
    Queue<Integer> queue;
    double sum;

    public MovingAverage(int size) {
        // do intialization if necessary
        queue = new LinkedList<>();
        this.size = size;
        sum = 0;
    }

    /*
     * @param val: An integer
     * @return:  
     */
    public double next(int val) {
        // write your code here
        queue.offer(val);
        sum += val;

        if (queue.size() > size) {
            int curr = queue.poll();
            sum -= curr;
        }

        return sum / queue.size();
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */