调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

给你一个整数数组 instructions ,你需要根据 instructions 中的元素创建一个有序数组。一开始你有一个空的数组 nums ,你需要 从左到右 遍历 instructions 中的元素,将它们依次插入 nums 数组中。每一次插入操作的 代价 是以下两者的 较小值 :

  • nums 中 严格小于  instructions[i] 的数字数目。
  • nums 中 严格大于  instructions[i] 的数字数目。

比方说,如果要将 3 插入到 nums = [1,2,3,5] ,那么插入操作的 代价 为 min(2, 1) (元素 1 和  2 小于 3 ,元素 5 大于 3 ),插入后 nums 变成 [1,2,3,3,5] 。

请你返回将 instructions 中所有元素依次插入 nums 后的 总最小代价 。由于答案会很大,请将它对 109 + 7 取余 后返回。

 

示例 1:

输入:instructions = [1,5,6,2]
输出:1
解释:一开始 nums = [] 。
插入 1 ,代价为 min(0, 0) = 0 ,现在 nums = [1] 。
插入 5 ,代价为 min(1, 0) = 0 ,现在 nums = [1,5] 。
插入 6 ,代价为 min(2, 0) = 0 ,现在 nums = [1,5,6] 。
插入 2 ,代价为 min(1, 2) = 1 ,现在 nums = [1,2,5,6] 。
总代价为 0 + 0 + 0 + 1 = 1 。

示例 2:

输入:instructions = [1,2,3,6,5,4]
输出:3
解释:一开始 nums = [] 。
插入 1 ,代价为 min(0, 0) = 0 ,现在 nums = [1] 。
插入 2 ,代价为 min(1, 0) = 0 ,现在 nums = [1,2] 。
插入 3 ,代价为 min(2, 0) = 0 ,现在 nums = [1,2,3] 。
插入 6 ,代价为 min(3, 0) = 0 ,现在 nums = [1,2,3,6] 。
插入 5 ,代价为 min(3, 1) = 1 ,现在 nums = [1,2,3,5,6] 。
插入 4 ,代价为 min(3, 2) = 2 ,现在 nums = [1,2,3,4,5,6] 。
总代价为 0 + 0 + 0 + 0 + 1 + 2 = 3 。

示例 3:

输入:instructions = [1,3,3,3,2,4,2,1,2]
输出:4
解释:一开始 nums = [] 。
插入 1 ,代价为 min(0, 0) = 0 ,现在 nums = [1] 。
插入 3 ,代价为 min(1, 0) = 0 ,现在 nums = [1,3] 。
插入 3 ,代价为 min(1, 0) = 0 ,现在 nums = [1,3,3] 。
插入 3 ,代价为 min(1, 0) = 0 ,现在 nums = [1,3,3,3] 。
插入 2 ,代价为 min(1, 3) = 1 ,现在 nums = [1,2,3,3,3] 。
插入 4 ,代价为 min(5, 0) = 0 ,现在 nums = [1,2,3,3,3,4] 。
​​​​​插入 2 ,代价为 min(1, 4) = 1 ,现在 nums = [1,2,2,3,3,3,4] 。
插入 1 ,代价为 min(0, 6) = 0 ,现在 nums = [1,1,2,2,3,3,3,4] 。
插入 2 ,代价为 min(2, 4) = 2 ,现在 nums = [1,1,2,2,2,3,3,3,4] 。
总代价为 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4 。

 

提示:

  • 1 <= instructions.length <= 105
  • 1 <= instructions[i] <= 105
通过次数
5.9K
提交次数
11.4K
通过率
51.7%


相关企业

提示 1
This problem is closely related to finding the number of inversions in an array

提示 2
if i know the position in which i will insert the i-th element in I can find the minimum cost to insert it


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
instructions =
[1,5,6,2]
Source