LeetCode 1005. K 次取反后最大化的数组和

Categories:

题目描述
思路分析
1. 解法一：排序 + 贪心（推荐）
相似题目

题目描述

✅ 1005. K 次取反后最大化的数组和

思路分析

解法一：排序 + 贪心（推荐）

核心思路：

将数组升序排序，优先翻转负数以增大总和。

负数翻完后若剩余次数为奇数，翻转绝对值最小的元素。

这样能保证每一步都取得最大增益。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(1)（忽略排序开销）。

import java.util.*;

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);

        int i = 0;
        while (i < nums.length && nums[i] < 0 && k > 0) {
            nums[i] = -nums[i];
            i++;
            k--;
        }

        int minIdx = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] < nums[minIdx]) {
                minIdx = j;
            }
        }

        if (k % 2 == 1) {
            nums[minIdx] = -nums[minIdx];
        }

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }
}

import "sort"

func largestSumAfterKNegations(nums []int, k int) int {
    sort.Ints(nums)

    i := 0
    for i < len(nums) && nums[i] < 0 && k > 0 {
        nums[i] = -nums[i]
        i++
        k--
    }

    minIdx := 0
    for j := 1; j < len(nums); j++ {
        if nums[j] < nums[minIdx] {
            minIdx = j
        }
    }

    if k%2 == 1 {
        nums[minIdx] = -nums[minIdx]
    }

    sum := 0
    for _, v := range nums {
        sum += v
    }
    return sum
}

相似题目

题目	难度	考察点
455. 分发饼干	简单	贪心
861. 翻转矩阵后的得分	中等	贪心
1402. 做菜顺序	困难	贪心
135. 分发糖果	困难	贪心
948. 令牌放置	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/64807548