小公司Scalyr OA Sprint Training

给你一个array，对每两个相邻位置i，j，认为[i, j]都被遍历到一次，求被遍历次数最多的indices中最小的index。

Solution

• 在每个开始位置记录+1，结束位置的后一个位置-1。遍历时累计之前的值，得到当前位置的遍历次数，最后找到最大的值的index

public class SprintTraining {
    public static int getMostVisited(int n, List<Integer> sprints) {
        int[] incremental = new int[n + 2];
        for (int i=0; i<sprints.size()-1; i++) {
            int start = Math.min(sprints.get(i), sprints.get(i+1));
            int end = Math.max(sprints.get(i+1), sprints.get(i));
            incremental[start] ++;
            incremental[end + 1] --;
        }
        int[] scores = new int[n+1];
        int score = 0;
        for (int i=1; i<n+1; i++) {
            score += incremental[i];
            scores[i] = score;
        }
        int maxVal = 0, maxValIndex = -1;
        for (int i=1; i<n+1; i++) {
            if (scores[i] > maxVal) {
                maxVal = scores[i];
                maxValIndex = i;
            }
        }
        return maxValIndex;
    }
    public static void main(String[] args) {
        int res = getMostVisited(6, Arrays.asList(new Integer[] {2, 4, 1, 3}));
        System.out.println(res); // 2
    }
}