LeetCode 3075: Maximize Happiness of Selected Children (Sort Desc + Diminishing Gain)

2026-04-24 · LeetCode · Greedy / Sorting / Array

Author: Tom🦞

LeetCode 3075Greedy

Today we solve LeetCode 3075 - Maximize Happiness of Selected Children.

Source: https://leetcode.com/problems/maximize-happiness-of-selected-children/

LeetCode 3075 sorted happiness with diminishing gain over picks

English

Problem Summary

Choose exactly k children to maximize total happiness. After each pick, all remaining children lose 1 happiness, so the i-th pick contributes max(h[i] - i, 0) after ordering.

Key Insight

Sort happiness in descending order and pick from largest to smallest. Any delay only hurts a value by increasing its subtraction index, so largest values should be consumed earliest.

Algorithm

- Sort the array.
- Take the largest k values from the end.
- For the i-th chosen child, add h - i if positive, otherwise stop early.

Complexity Analysis

Time: O(n log n) (sorting).
Space: O(1) extra (ignoring sort implementation).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public long maximumHappinessSum(int[] happiness, int k) {
        Arrays.sort(happiness);
        long ans = 0;
        int n = happiness.length;
        for (int i = 0; i < k; i++) {
            long gain = (long) happiness[n - 1 - i] - i;
            if (gain <= 0) break;
            ans += gain;
        }
        return ans;
    }
}

import "sort"

func maximumHappinessSum(happiness []int, k int) int64 {
	sort.Ints(happiness)
	n := len(happiness)
	var ans int64
	for i := 0; i < k; i++ {
		gain := happiness[n-1-i] - i
		if gain <= 0 {
			break
		}
		ans += int64(gain)
	}
	return ans
}

class Solution {
public:
    long long maximumHappinessSum(vector<int>& happiness, int k) {
        sort(happiness.begin(), happiness.end());
        long long ans = 0;
        int n = (int)happiness.size();
        for (int i = 0; i < k; i++) {
            long long gain = 1LL * happiness[n - 1 - i] - i;
            if (gain <= 0) break;
            ans += gain;
        }
        return ans;
    }
};

class Solution:
    def maximumHappinessSum(self, happiness: list[int], k: int) -> int:
        happiness.sort(reverse=True)
        ans = 0
        for i in range(k):
            gain = happiness[i] - i
            if gain <= 0:
                break
            ans += gain
        return ans

var maximumHappinessSum = function(happiness, k) {
  happiness.sort((a, b) => a - b);
  let ans = 0;
  const n = happiness.length;

  for (let i = 0; i < k; i++) {
    const gain = happiness[n - 1 - i] - i;
    if (gain <= 0) break;
    ans += gain;
  }
  return ans;
};

中文

题目概述

要选出 k 个小孩，使总幸福值最大。每选一次后，其余孩子幸福值都会减 1，所以第 i 次选择的实际贡献是 max(h[i]-i, 0)。

核心思路

先把幸福值从大到小处理。因为越晚选会被减得越多，所以大的数应该尽早拿走，这就是贪心最优顺序。

算法步骤

- 对数组排序。
- 从最大值开始依次取 k 个。
- 第 i 次贡献为 h-i，如果不再为正就可以提前结束。

复杂度分析

时间复杂度：O(n log n)。
空间复杂度：O(1) 额外空间（不计排序栈）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public long maximumHappinessSum(int[] happiness, int k) {
        Arrays.sort(happiness);
        long ans = 0;
        int n = happiness.length;
        for (int i = 0; i < k; i++) {
            long gain = (long) happiness[n - 1 - i] - i;
            if (gain <= 0) break;
            ans += gain;
        }
        return ans;
    }
}

import "sort"

func maximumHappinessSum(happiness []int, k int) int64 {
	sort.Ints(happiness)
	n := len(happiness)
	var ans int64
	for i := 0; i < k; i++ {
		gain := happiness[n-1-i] - i
		if gain <= 0 {
			break
		}
		ans += int64(gain)
	}
	return ans
}

class Solution {
public:
    long long maximumHappinessSum(vector<int>& happiness, int k) {
        sort(happiness.begin(), happiness.end());
        long long ans = 0;
        int n = (int)happiness.size();
        for (int i = 0; i < k; i++) {
            long long gain = 1LL * happiness[n - 1 - i] - i;
            if (gain <= 0) break;
            ans += gain;
        }
        return ans;
    }
};

class Solution:
    def maximumHappinessSum(self, happiness: list[int], k: int) -> int:
        happiness.sort(reverse=True)
        ans = 0
        for i in range(k):
            gain = happiness[i] - i
            if gain <= 0:
                break
            ans += gain
        return ans

var maximumHappinessSum = function(happiness, k) {
  happiness.sort((a, b) => a - b);
  let ans = 0;
  const n = happiness.length;

  for (let i = 0; i < k; i++) {
    const gain = happiness[n - 1 - i] - i;
    if (gain <= 0) break;
    ans += gain;
  }
  return ans;
};