收集巧克力

You are given a 0-indexed integer array nums of size n representing the cost of collecting different chocolates. The cost of collecting the chocolate at the index i is nums[i]. Each chocolate is of a different type, and initially, the chocolate at the index i is of ith type.

In one operation, you can do the following with an incurred cost of x:

• Simultaneously change the chocolate of ith type to ((i + 1) mod n)th type for all chocolates.

Return the minimum cost to collect chocolates of all types, given that you can perform as many operations as you would like.

 

Example 1:

Input: nums = [20,1,15], x = 5
Output: 13
Explanation: Initially, the chocolate types are [0,1,2]. We will buy the 1st type of chocolate at a cost of 1.
Now, we will perform the operation at a cost of 5, and the types of chocolates will become [1,2,0]. We will buy the 2nd type of chocolate at a cost of 1.
Now, we will again perform the operation at a cost of 5, and the chocolate types will become [2,0,1]. We will buy the 0th type of chocolate at a cost of 1. 
Thus, the total cost will become (1 + 5 + 1 + 5 + 1) = 13. We can prove that this is optimal.

Example 2:

Input: nums = [1,2,3], x = 4
Output: 6
Explanation: We will collect all three types of chocolates at their own price without performing any operations. Therefore, the total cost is 1 + 2 + 3 = 6.

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 109
• 1 <= x <= 109

/*
 * 题目思路：
 * 使用Java Stream API来实现相同的逻辑。
 * 我们依然需要通过旋转巧克力的类型数组来找到最小的收集成本。
 */

import java.util.stream.IntStream;

public class ChocolateCollectionStream {
    public int minCost(int[] nums, int x) {
        int n = nums.length;
        int[] rotatedCosts = new int[n];
        System.arraycopy(nums, 0, rotatedCosts, 0, n);
        return IntStream.range(0, n)
                .map(rotate -> {
                    int currentCost = IntStream.of(rotatedCosts).sum();
                    for (int i = 0; i < n; i++) {
                        rotatedCosts[i] = Math.min(rotatedCosts[i], nums[(i + rotate + 1) % n]);
                    }
                    return currentCost + rotate * x;
                })
                .min()
                .orElse(Integer.MAX_VALUE);
    }
}

该题解运用了单调栈与差分数组的组合技术来寻找最小化收集所有类型巧克力的成本。首先，题解初始化了一个单调栈来存储三元组，每个三元组包含当前巧克力的成本、原始索引和栈中能够影响到的最远索引。接着，使用差分数组dif来跟踪成本变化，每次将最小的成本巧克力对应的成本加到差分数组中，并在必要时调整以保持栈的单调性。最后，通过两次累加差分数组来计算每种操作下的总成本，并找出最小成本。在这个过程中，算法通过从最小成本的巧克力开始，逐步调整和计算操作后的成本，以求得最优解。

O(n)

O(n)