LintCode 1678 · Train compartment problem.java

	public class Solution {
	/**
	* @param arr: the arr
	* @return: the number of train carriages in this transfer station with the largest number of train carriages
	*/
	public int trainCompartmentProblem(int[] arr) {
	// Handle corner cases
	if (arr == null || arr.length == 0) {
	return 0;
	}
	int maxCount = 0;
	int n = arr.length, j = 0;
	Stack<Integer> stack = new Stack<>();
	for (int i = 0; i < n; i++) {
	if (i + 1 == arr[j]) {
	// bypass directly???
	j++;
	} else {
	stack.push(i + 1);
	maxCount = Math.max(maxCount, stack.size());
	}
	while (j < n && !stack.isEmpty() && stack.peek() == arr[j]) {
	stack.pop();
	j++;
	}
	}
	if (j == n) {
	// done all pop
	return maxCount;
	} else {
	return -1;
	}
	}
	}

view raw LintCode 1678 · Train compartment problem.java hosted with ❤ by GitHub