LintCode 751 · John's business.java

	public class Solution {
	/**
	* @param A: The prices [i]
	* @param k:
	* @return: The ans array
	*/
	public int[] business(int[] A, int k) {
	// handle corner cases
	if (A == null || A.length == 0) {
	return new int[0];
	}
	int n = A.length;
	int[] profit = new int[n];
	Queue<Integer> minHeap = new PriorityQueue<>();
	// init the first 0..k-1 prices into the minHeap
	for (int i = 0; i < k; i++) {
	minHeap.add(A[i]);
	}
	// core logic - keep sliding the window,
	// update the minHeap by removing the left most outdated, and adding the right most new addition.
	// then always take the current price, the A[i], and subtract that to the minHeap.peek(),
	// otherwise if it's not profitable, just use zero. indicating that you don't take that deal for a loss.
	for (int i = 0; i < n; i++) {
	if (i - k - 1 >= 0) {
	minHeap.remove(A[i - k - 1]);
	}
	if (i + k < n) {
	minHeap.add(A[i + k]);
	}
	profit[i] = Math.max(0, A[i] - minHeap.peek());
	// System.out.println("minHeap = " + minHeap);
	}
	return profit;
	}
	}

view raw LintCode 751 · John's business.java hosted with ❤ by GitHub