Sliding Window (Java) - ShuweiLeung/Thinking GitHub Wiki

1.（480:Hard）（非常非常经典题）Sliding Window Median

  1. Use two Heaps to store numbers. maxHeap for numbers smaller than current median, minHeap for numbers bigger than and equal to current median. A small trick I used is always make size of minHeap equal (when there are even numbers) or 1 element more (when there are odd numbers) than the size of maxHeap. Then it will become very easy to calculate current median.
  2. Keep adding number from the right side of the sliding window and remove number from left side of the sliding window. And keep adding current median to the result.
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(
        new Comparator<Integer>() {
            public int compare(Integer i1, Integer i2) {
                return i2.compareTo(i1);
            }
        }
    );
	
    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++) {
            if (i >= k) {
        	result[i - k] = getMedian();
        	remove(nums[i - k]);
            }
            if (i < nums.length) {
        	add(nums[i]);
            }
        }
        
        return result;
    }
    
    private void add(int num) {
	if (num < getMedian()) {
	    maxHeap.add(num);
	}
	else {
	    minHeap.add(num);
	}
	if (maxHeap.size() > minHeap.size()) {
            minHeap.add(maxHeap.poll());
	}
        if (minHeap.size() - maxHeap.size() > 1) {
            maxHeap.add(minHeap.poll());
        }
    }
	
    private void remove(int num) {
	if (num < getMedian()) {
	    maxHeap.remove(num);
	}
	else {
	    minHeap.remove(num);
	}
	if (maxHeap.size() > minHeap.size()) {
            minHeap.add(maxHeap.poll());
	}
        if (minHeap.size() - maxHeap.size() > 1) {
            maxHeap.add(minHeap.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)minHeap.peek();
	}
    }
⚠️ **GitHub.com Fallback** ⚠️