LeetCode 1090. 受标签影响的最大值

Categories:

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

题目描述

✅ 1090. 受标签影响的最大值

思路分析

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

核心思路：

按值从大到小排序，优先选择更大的元素。

对每个标签维护已选数量，超过 useLimit 则跳过。

直到选够 numWanted 个或遍历结束。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示元素数量。

空间复杂度：O(n)，用于排序索引与标签计数。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        Integer[] idx = new Integer[values.length];
        for (int i = 0; i < values.length; i++) {
            idx[i] = i;
        }

        Arrays.sort(idx, (a, b) -> values[b] - values[a]);

        Map<Integer, Integer> cnt = new HashMap<>();
        int picked = 0;
        int sum = 0;

        for (int id : idx) {
            if (picked == numWanted) {
                break;
            }
            int label = labels[id];
            int used = cnt.getOrDefault(label, 0);
            if (used == useLimit) {
                continue;
            }

            cnt.put(label, used + 1);
            sum += values[id];
            picked++;
        }

        return sum;
    }
}

import "sort"

func largestValsFromLabels(values []int, labels []int, numWanted int, useLimit int) int {
	idx := make([]int, len(values))
	for i := 0; i < len(values); i++ {
		idx[i] = i
	}

	sort.Slice(idx, func(i, j int) bool {
		return values[idx[i]] > values[idx[j]]
	})

	cnt := make(map[int]int)
	picked := 0
	sum := 0

	for _, id := range idx {
		if picked == numWanted {
			break
		}
		label := labels[id]
		used := cnt[label]
		if used == useLimit {
			continue
		}

		cnt[label] = used + 1
		sum += values[id]
		picked++
	}

	return sum
}

相似题目

题目	难度	考察点
1090. 受标签影响的最大值	中等	贪心、排序
1353. 最多可以参加的会议数目	中等	贪心
870. 优势洗牌	中等	贪心、排序
1710. 卡车上的最大单元数	简单	贪心
1217. 玩筹码	简单	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/68910710