出差来回机票钱最少

实现一个函数public int minPrice(int[] departing, int[] returning, int minDays, int maxDays)，其中departing代表出发时的机票价格，returning代表回来时的机票价格，出发的时间介于minDays和maxDays之间，求出差花费的最少的机票钱。

例子：
departing = [5, 2, 3, 1, 1]
returning = [0, 1, 5, 2, 1]
minDays = 1
maxDays = 4
答案：2

• 解法1：暴力解法
  两层for循环，先确定出发的日期i，再确定返回的日期时j属于[i + minDays, i + maxDays]，然后求最少的机票钱，但这样会超时。

• 解法2：单调队列
  每次固定出发日期i，都是求returning中一个窗口returning[i + minDays, i + maxDays]中机票钱的最少值，于是联想到单调队列求这个可以达到O(n)的复杂度。
  注意如队列的是i，而不是returning[i]，这样在将队列中超期的数字移出队列的时候更好判断一些。

    public int minPrice(int[] departing, int[] returning, int minDays, int maxDays) {
        int n = departing.length;
        int duration = maxDays - minDays;

        int[] minReturns = new int[n - minDays];
        int count = 0;
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = minDays; i < n; i++) {
            while (!queue.isEmpty() && returning[queue.peekLast()] >= returning[i]) {
                queue.pollLast();
            }

            if (!queue.isEmpty() && queue.peekFirst() < (i - duration)) {
                queue.pollFirst();
            }

            queue.addLast(i);

            if (i < maxDays) {
                continue;
            }

            minReturns[count++] = returning[queue.peekFirst()];
        }

        for (int i = 0; i < duration; i++) {
            if (!queue.isEmpty() && queue.peekFirst() < (i - duration)) {
                queue.pollFirst();
            }

            minReturns[count++] = returning[queue.peekFirst()];
        }
        // int min = Integer.MAX_VALUE;
        // for (int i = 0; i < duration; i++) {
        //     min = Math.min(min, returning[n - 1 - i]);
        //     minReturns[minReturns.length - 1 - i] = min;
        // }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < minReturns.length; i++) {
            min = Math.min(min, departing[i] + minReturns[i]);
        }
        return min;
    }

    public static void main(String[] args) {
        System.out.println(new MinPrice().minPrice(new int[] {5, 2, 3, 1, 1}, new int[] {0, 1, 5, 2, 1}, 2, 3) == 3);
        System.out.println(new MinPrice().minPrice(new int[] {1, 2, 3, 1, 1}, new int[] {0, 1, 5, 2, 1}, 1, 4) == 2);
        System.out.println(new MinPrice().minPrice(new int[] {1, 2, 3, 1, 1}, new int[] {0, 1, 5, 2, 1}, 1, 1) == 2);
        System.out.println(new MinPrice().minPrice(new int[] {1, 2, 3, 1, 1}, new int[] {0, 1, 5, 2, 1}, 2, 2) == 4);
        System.out.println(new MinPrice().minPrice(new int[] {1, 2, 3, 1, 1}, new int[] {0, 1, 5, 2, 1}, 4, 4) == 2);

        System.out.println(new MinPrice().minPrice(new int[] {1, 2, 3, 4, 5}, new int[] {0, 1, 5, 2, 1}, 2, 2) == 4);
        System.out.println(new MinPrice().minPrice(new int[] {5, 4, 3, 2, 1}, new int[] {0, 1, 5, 2, 1}, 2, 2) == 4);
        System.out.println(new MinPrice().minPrice(new int[] {5, 4, 3, 2, 1}, new int[] {1, 2, 3, 4, 5}, 2, 2) == 8);
        System.out.println(new MinPrice().minPrice(new int[] {5, 2, 3, 1, 1}, new int[] {1, 2, 3, 4, 5}, 2, 2) == 6);
        System.out.println(new MinPrice().minPrice(new int[] {5, 2, 3, 1, 1}, new int[] {5, 4, 3, 1, 1}, 2, 2) == 3);

        System.out.println(new MinPrice().minPrice(new int[] {1, 1, 1, 1, 1}, new int[] {5, 4, 3, 1, 1}, 2, 2) == 2);
        System.out.println(new MinPrice().minPrice(new int[] {5, 2, 3, 1, 1}, new int[] {1, 1, 1, 1, 1}, 2, 2) == 3);
        System.out.println(new MinPrice().minPrice(new int[] {5, 2, 3, 1, 1}, new int[] {1, 1, 2, 1, 1}, 2, 2) == 3);

        System.out.println(new MinPrice().minPrice(new int[] {5, 2, 3, 1, 1}, new int[] {1, 1, 2, 1, 1}, 1, 2) == 2);
        System.out.println(new MinPrice().minPrice(new int[] {5, 2, 3, 1, 1}, new int[] {1, 1, 2, 1, 1}, 1, 3) == 2);
        System.out.println(new MinPrice().minPrice(new int[] {5, 2, 3, 1, 1}, new int[] {1, 1, 2, 1, 1}, 1, 4) == 2);
        System.out.println(new MinPrice().minPrice(new int[] {5, 2, 3, 1, 1}, new int[] {1, 1, 2, 1, 1}, 2, 3) == 3);
        System.out.println(new MinPrice().minPrice(new int[] {5, 2, 3, 1, 1}, new int[] {1, 1, 2, 1, 1}, 2, 4) == 3);
        System.out.println(new MinPrice().minPrice(new int[] {5, 2, 3, 1, 1}, new int[] {1, 1, 2, 1, 1}, 4, 4) == 6);
    }