Apple OA 面试真题解析：Modify an Array——最小代价排序数组

Modify an Array

Given an array of integers, the cost to change an element is the absolute difference between its initial value and its new value. For example, if the element is initially 10, it can be changed to 7 or 13 for a cost of 3. Determine the minimum cost to sort the array either ascending or descending along its length.

Example

n = 6
arr = [0, 1, 2, 5, 6, 5, 7]

• Only arr[5] = 5 violates the order for an ascending sort.
• If the value 5 is increased to 6, the array will be sorted in ascending order: arr' = [0, 1, 2, 5, 6, 6, 7].
• The cost is |arr[5] - arr'[5]| = |5 - 6| = 1.

这道题的核心是把数组变成单调递增或单调递减，并且每个元素修改的代价等于修改前后的绝对差值。由于题目要求的是“最小代价”，通常需要分别计算升序和降序两种目标下的最优修改方案，再取较小值。对于给定位置，只有在它破坏整体顺序时才需要调整，因此常见做法是先扫描数组，找出需要被拉高或压低的部分，再结合动态规划或前后缀最优值来累计最小成本。样例中只有一个元素不满足升序条件，把它从 5 调整到 6 后即可完成排序，总代价为 1。