class Solution {
public:
int convertArray(vector<int>& nums) {
}
};
2263. 数组变为有序的最小操作次数
给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以：
0 <= i < nums.length 内选出一个下标 inums[i] 的值变为 nums[i] + 1 或 nums[i] - 1返回将数组 nums 变为 非递增 或 非递减 所需的 最小 操作次数。
示例 1：
输入：nums = [3,2,4,5,0] 输出：4 解释： 一种可行的操作顺序，能够将 nums 变为非递增排列： - nums[1] 加 1 一次，使其变为 3 。 - nums[2] 减 1 一次，使其变为 3 。 - nums[3] 减 1 两次，使其变为 3 。 经过 4 次操作后，nums 变为 [3,3,3,3,0] ，按非递增顺序排列。 注意，也可以用 4 步操作将 nums 变为 [4,4,4,4,0] ，同样满足题目要求。 可以证明最少需要 4 步操作才能将数组变为非递增或非递减排列。
示例 2：
输入：nums = [2,2,3,4] 输出：0 解释：数组已经是按非递减顺序排列了，无需执行任何操作，返回 0 。
示例 3：
输入：nums = [0] 输出：0 解释：数组已经是按非递减顺序排列了，无需执行任何操作，返回 0 。
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1000
进阶：你可以设计并实现时间复杂度为 O(n*log(n)) 的解法吗?
原站题解
golang 解法, 执行用时: 64 ms, 内存消耗: 2.6 MB, 提交时间: 2023-10-17 21:55:14
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func decrease(nums []int) int {
dp := make([]int, 1001)
maximum := make([]int, 1001)
for i := 1000; i >= 0; i-- {
dp[i] = abs(nums[0] - i)
if i == 1000 {
maximum[i] = dp[i]
} else {
maximum[i] = min(dp[i], maximum[i+1])
}
}
for i := 1; i < len(nums); i++ {
for j := 1000; j >= 0; j-- {
dp[j] = maximum[j] + abs(nums[i]-j)
if j == 1000 {
maximum[j] = dp[j]
} else {
maximum[j] = min(dp[j], maximum[j+1])
}
}
}
return maximum[0]
}
func increase(nums []int) int {
dp := make([]int, 1001)
minimum := make([]int, 1001)
for i := 0; i < 1001; i++ {
dp[i] = abs(nums[0] - i)
if i == 0 {
minimum[i] = dp[i]
} else {
minimum[i] = min(dp[i], minimum[i-1])
}
}
for i := 1; i < len(nums); i++ {
for j := 0; j < 1001; j++ {
dp[j] = minimum[j] + abs(nums[i]-j)
if j == 0 {
minimum[j] = dp[j]
} else {
minimum[j] = min(dp[j], minimum[j-1])
}
}
}
return minimum[1000]
}
func convertArray(nums []int) int {
return min(increase(nums), decrease(nums))
}
java 解法, 执行用时: 26 ms, 内存消耗: 39.9 MB, 提交时间: 2023-10-17 21:53:42
class Solution {
public int convertArray(int[] nums) {
int n = nums.length;
int[] copy = Arrays.copyOf(nums,n);
Arrays.sort(copy);
int ans = getAns(nums,copy);
reverse(copy);
ans = Math.min(ans,getAns(nums,copy));
return ans;
}
private int getAns(int[] nums, int[] copy){
int n = nums.length;
int[] dp = new int[n];
for(int num:nums){
int min = Integer.MAX_VALUE;
for(int j = 0; j < n; j++){
min = Math.min(min,dp[j]);
dp[j]=min+Math.abs(num-copy[j]);
}
}
int ans = Integer.MAX_VALUE;
for(int v:dp){
ans = Math.min(v,ans);
}
return ans;
}
private void reverse(int []arr){
int n = arr.length;
for(int i=0,j=n-1;i<j;i++,j--){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
// 堆
class Solution2 {
public int convertArray(int[] nums) {
return Math.min(helper(nums),helper(reverse(nums)));
}
private int helper(int[] nums){
int res = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->b-a);
for(int num:nums){
if(!pq.isEmpty()){
int preMax = pq.peek();
if(preMax>num){
res+= preMax-num;
pq.offer(num);
pq.poll();
}
}
pq.offer(num);
}
return res;
}
private int[] reverse(int []arr){
int n = arr.length;
for(int i=0,j=n-1;i<j;i++,j--){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return arr;
}
}
// 堆 + 压缩
class Solution3 {
public int convertArray(int[] nums) {
return Math.min(helper(nums),helper(reverse(nums)));
}
private int helper(int[] nums){
int res = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->b-a);
int[] map = new int[1001];
for(int num:nums){
int time = map[num]+1;
if(!pq.isEmpty()){
int pre = pq.peek();
if(pre>num){
res+= pre-num;
++time;
if(map[pre]==1) pq.poll();
--map[pre];
}
}
if(map[num]==0) pq.offer(num);
map[num]=time;
}
return res;
}
private int[] reverse(int []arr){
int n = arr.length;
for(int i=0,j=n-1;i<j;i++,j--){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return arr;
}
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 10.2 MB, 提交时间: 2023-10-17 21:52:13
class Solution {
public:
int solve(vector<int>& nums) {
priority_queue<int, vector<int>, less<int>> ll;
auto ans = 0;
for (auto e : nums) {
if (!ll.empty() && e < ll.top()) {
ans += ll.top() - e;
ll.pop();
ll.emplace(e); // 为了保证斜率变化连续，一定要多添加一个左端点
}
ll.emplace(e);
}
return ans;
}
int convertArray(vector<int>& nums) {
int a1 = solve(nums);
reverse(nums.begin(), nums.end());
return min(a1, solve(nums));
}
// 基于dp
int convertArray2(vector<int>& nums) {
//递增
//f[i][j] 维护结果结果即可
int ans = solve2(nums);
reverse(nums.begin(),nums.end());
ans = min(ans, solve2(nums));
return ans;
}
int solve2(vector<int>&nums) {
int n = nums.size();
int dp[n][1001];
memset(dp,0,sizeof(dp));
int ans = INT_MAX;
for(int j = 0;j <= 1000;j++) {
//<= j 结尾的最小变化值
dp[0][j] = abs(nums[0] - j);
if(j)dp[0][j] = min(dp[0][j],dp[0][j - 1]);
if(n == 1)ans = min(ans,dp[0][j]);
}
for(int i = 1;i < n;i++) {
for(int j = 0;j <= 1000;j++) {
dp[i][j] = dp[i - 1][j] + abs(nums[i] - j);
if(j)dp[i][j] = min(dp[i][j],dp[i][j - 1]);
if(i == n - 1)ans = min(ans,dp[i][j]);
}
}
return ans;
}
};
python3 解法, 执行用时: 52 ms, 内存消耗: 16.3 MB, 提交时间: 2023-10-17 21:48:21
class Solution:
def convertArray(self, nums: List[int]) -> int:
def helper(nums: List[int]) -> int:
"""变为不减数组的最小操作次数"""
res, pq = 0, [] # 大根堆
for num in nums:
if not pq:
heappush(pq, -num)
else:
preMax = -pq[0]
if preMax > num:
res += preMax - num
heappushpop(pq, -num)
heappush(pq, -num)
return res
return min(helper(nums), helper(nums[::-1]))
def convertArray2(self, nums: List[int]) -> int:
def helper(nums: List[int]) -> int:
"""变为不减数组的最小操作次数"""
n, max_ = len(nums), max(nums)
dp = [[int(1e20)] * (max_ + 1) for _ in range(n)] # dp[i][num] 表示 前i个元素最num结尾的最小的代价是多少
for j in range((max_ + 1)):
dp[0][j] = abs(nums[0] - j)
for i in range(1, n):
preMin = int(1e20)
for j in range((max_ + 1)):
preMin = min(preMin, dp[i - 1][j])
dp[i][j] = preMin + abs(nums[i] - j)
return min(dp[-1])
return min(helper(nums), helper(nums[::-1]))
def convertArray3(self, nums: List[int]) -> int:
def helper(nums: List[int]) -> int:
"""变为不减数组的最小操作次数
取得最小的操作次数时，数组末尾元素必须等于原数组中的某个元素
dp[i][num]表示前i个元素以num结尾的最小的代价是多少 时间复杂度 O(n*max(num[i]))
"""
n = len(nums)
allNums = sorted(set(nums))
m = len(allNums)
dp = [[int(1e20)] * m for _ in range(n)]
for j in range((m)):
dp[0][j] = abs(nums[0] - allNums[j])
for i in range(1, n):
preMin = int(1e20)
for j in range(m):
preMin = min(preMin, dp[i - 1][j])
dp[i][j] = preMin + abs(nums[i] - allNums[j])
return min(dp[-1])
return min(helper(nums), helper(nums[::-1]))