The manager of the Amazon warehouse has decided to make changes to the inventory. Currently, the inventory has n products, where the quality of the i-th product after quality checks is represented by the array element quality[i].
The manager wants to create an optimal inventory, where the array of products quality follows this property:
- All occurrences of each quality value must be contiguous.
In order to convert the inventory into an optimal inventory, the manager can do the following operation any number of times:
- Choose two quality values
xandy. - Replace every product with quality
xto have qualityyinstead. - This operation costs
num_replacementsunits of money, wherenum_replacementsis the number of products whose quality was changed.
Given n products and an array quality, find the minimum amount of money the manager has to spend to convert the inventory into an optimal inventory.
Note: The quality of a product can be negative, indicating that the product is of poor quality.
Example:
Given n = 7, quality = [7, 7, 5, 7, 3, 5, 3].
One of the optimal ways to convert is explained below:
- Replace all products of quality
5with7, and then replace all products of quality3with7.
Hence, the total amount spent is 4.
Function Description
Complete the function getMinAmount in the editor below.
getMinAmount has the following parameter(s):
int quality[n]: the quality of products
Returns
int: the minimum amount of money the manager has to spend to convert the inventory into an optimal inventory.
这道 Amazon OA 题的核心是：把数组变成“相同数值都连续出现”的最优库存，并让替换代价最小。关键观察是，最终保留下来的应该是一段段连续的相同值块；对于每一种数值，只要它在数组中出现的多个位置不连续，就说明中间夹着别的值，需要通过合并或替换来消除这些“断点”。常见做法是先统计每个值的出现次数、首次和末次位置，再把数组按值的连续区间进行分组，计算每个区间内需要保留的最大重复量，从而得到最少替换次数。该题本质上结合了哈希统计和区间扫描，示例中通过把 5 和 3 逐步并入 7，最终代价为 4。
