刚才我问DS，算法太难了，我们还有必要学算法吗？我们该怎么办？

DS说，我们还是有必要学，但是都需要3-6个月，好难呀。

贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）

一、贪心算法定义

说白了，贪心算法可以理解为一种特殊的动态规划问题，拥有一些更特殊的性质，可以进一步降低动态规划算法的时间复杂度。 -- labuladong

贪心算法之区间调度问题

求最优类问题，贪心算法是求的局部最优解。将求解过程分成若干个步骤，每个步骤都用贪心原则，选取最优的选择。

1.1、贪心算法能够解决那些问题呢？

• 硬币找零问题：在某些硬币组合下，贪心算法总是可以得到最优解
• 区间调度问题：假设你有一些任务，每个任务在一段时间内进行，你的目标是完成尽可能多的任务。
• 分数背包问题：给定一组物品和一个载重量，你的目标是选择一组物品，使得总重量不超过载重量，且总价值最大
• 股票买卖问题：
• 霍夫曼编码：无损压缩数据的贪心算法。
• Dijkstra算法：它是一种解决给定源顶点到其余各顶点拿的最短路径问题的贪心算法。

15.1 贪心算法

二、贪心算法学习之路

直接码上灵神的题单：分享丨【题单】贪心算法（基本贪心策略/反悔/区间/字典序/数学/思维/构造）

开始学习ing!!!

贪心策略：

有两种基本贪心策略：

• 从最小/最大开始贪心，优先考虑最小/最大的数，从小到大/从大到小贪心。在此基础上，衍生出反悔贪心。
• 从最左/最优开始贪心，思考第一个数/最后一个数的贪心策略，把n个数的原问题转换成n-1个数（或更少）的字问题。

2.1、从最小/最大开始贪心

3074. 重新分装苹果（20250228）

简单理解题目：给出整数apple数组，表示需要转运的苹果数，给出整数capacity， capacity[i]表示第i个包裹最多可以存放i个苹果，问将apple数组里面的苹果转运使用capacity存放，最少需要多少个包裹。

需要求最少的包裹，肯定是先用最大的包裹来存放，然后依次往后选择。

题目说，同一个包裹中的苹果可以分装到不同的箱子中。那么按照容量从大到小选择箱子装苹果，直到所有的苹果均装入箱子为止。

注意题目保证可以将包裹中的苹果重新分装到箱子中，就是说sum(apple) >= sum(capacity)

Python

class Solution:
    def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
        total = sum(apple)
        capacity.sort(reverse=True)
        
        ans = 0 
        for x in capacity:
            if total <= 0:
                break
            total -= x
            ans += 1
        
        return ans

Java

class Solution {
    public int minimumBoxes(int[] apple, int[] capacity) {
        // 统计有多少个苹果
        int sum = 0;
        for (int x : apple) {
            sum += x;
        }
        // 排序
        Arrays.sort(capacity);
        int m = capacity.length;
        int i = m - 1; // 从后往前选

        while (sum > 0) {
            sum -= capacity[i--];
        }
        return m - i - 1;
    }
}

2279. 装满石头的背包的最大数量（20250228）

Python

class Solution:
    def maximumBags(
        self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        assert len(capacity) == len(rocks)
        rest = [cap - rock for cap, rock in zip(capacity, rocks)]
        rest.sort()

        for i in range(len(rest)):
            # 这里在调用的时候思想有点卡，就是循环rest，将add的石头剪掉，然后将rest[i]至为空
            if rest[i] > additionalRocks:
                break
            additionalRocks -= rest[i]
            rest[i] = 0

        return rest.count(0)

Java

class Solution {
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int n = capacity.length;
        int[] rest = new int[n];
        for (int i = 0; i < n; i++) {
            rest[i] = capacity[i] - rocks[i];
        }
        Arrays.sort(rest);
        // 这里为什么可以用ans？
        int ans = 0;
        for (int i = 0; i < rest.length; i++) {
            if (rest[i] > additionalRocks) {
                break;
            }
            additionalRocks -= rest[i];
            // 如果是0，也满足
            ans++;
        }
        return ans;

    }
}

1338. 数组大小减半（20250305）

• 用哈希表（或者数组）统计每个元素的出现次数
• 把出现次数从大到小排序，得到cnt数组
• 遍历cnt，计算前缀和s，直到 s >= (n/2)为止，返回此时的下标加一就是答案。

Java

class Solution {
    public int minSetSize(int[] arr) {
        // 求最大值
        int mx = 0;
        for (int num : arr) {
            mx = Math.max(mx, num);
        }
        // 构建最大值长度+1的数组
        int[] cnt = new int[mx + 1];
        for (int num : arr) {
            cnt[num]++;
        }
        // 排序
        Arrays.sort(cnt);
        int s = 0;
        // 从前往后遍历
        for (int i = mx;; i--) {
            // 统计前缀和
            s += cnt[i];
            if (s >= arr.length / 2) {
                return mx + 1 - i;
            }
        }
    }
}

Python

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        cnt = sorted(Counter(arr).values(), reverse=True)
        # 向下取整 7 // 2 = 3
        m = len(arr) // 2
        # itertools.accumulate()是求数组的前缀和
        for i, s in enumerate(accumulate(cnt)):
            if s >= m:
                return i + 1

1710. 卡车上的最大单元数（20250305）

看了半天题都没看懂，最后总算是理解了。

boxTypes[i][0]表示i类箱子有多少个，最多只能装boxTypes[i][0]个

Java

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        Arrays.sort(boxTypes, (a,b) -> b[1] - a[1]);
        int ans =0;
        for(int[] nums: boxTypes){
            if(nums[0] <= truckSize){
                ans += (nums[0] * nums[1]);
                truckSize -= nums[0];
            }
            else{
                ans += (truckSize * nums[1]);
                break;
            }
        }
        return ans;
    }
}

Python

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        # boxTypes[i][0]表示i类箱子有多少个，最多只能装boxTypes[i][0]个
        boxTypes.sort(key=lambda x: x[1], reverse=True)
        ans = 0
        for k,v in boxTypes:
            if k <= truckSize:
                ans += (k*v)
                truckSize -= k
            else:
                ans += (truckSize * v)
                break
        return ans

2587. 重排数组以得到最大前缀分数（20250305）

Java

class Solution {
    public int maxScore(int[] nums) {
        Arrays.sort(nums);
        int ans =0;
        // 使用long防止加法溢出
        long s= 0;
        for(int i = nums.length-1;i>=0;i--){
            int num = nums[i];
            s += num;
            if(s > 0){
                ans++;
            }
        }
        return ans;
    }
}

Python

class Solution:
    def maxScore(self, nums: List[int]) -> int:
      	# 要获取最多的整数，就需要从大到小排序
        nums.sort(reverse=True)
        # return sum(s > 0 for s in accumulate(nums))  # 这个也是求>0的个数
        return len([num for num in accumulate(nums) if num > 0])  # 这是求>0的个数

2.2、单序列配对

2144. 打折购买糖果的最小开销（20250305）

Java

class Solution {
    public int minimumCost(int[] cost) {
        Arrays.sort(cost);
        int ans = 0;
        for (int i = cost.length - 1; i >= 0; i -= 3) {
            ans += cost[i];
            if (i > 0) {
                ans += cost[i - 1];
            }
        }
        return ans;
    }
}

Python

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost.sort()
        n = len(cost)
        ans = 0
        # range(n-1, -1, -3) 表示从大往小遍历，最后一个值取不到，跨度为-3
        for i in range(n-1, -1, -3):
            # i, i-1
            ans += cost[i]
            if i > 0:
                ans += cost[i-1]
        return ans

1877. 数组中最大数对和的最小值（20250310更新）

Java

class Solution {
    public int minPairSum(int[] nums) {
        // 最大数组和最小，意思是在所有的情况下这个选出来的最大数对两个数相加是最小的
        // 那么肯定不能用最大的加最大的，那么就会变成最大
        // 就只会想到最大的和最小的匹配，才有可能出现最大数对，和最小
        Arrays.sort(nums);
        int m  = nums.length;
        int ans = nums[0] + nums[m-1];

        // for(int i = 0, j=m-1;i<j;i++, j--){
        //     ans = Math.max(ans, nums[i] + nums[j]);
        // }

        for(int i =0;i<m/2;i++){
            ans = Math.max(ans, nums[i] + nums[m-i-1]);
        }
        return ans; 
    }
}

Python

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()
        ans =0
        m = len(nums)
        for i in range(int(m/2)):
            ans = max(ans, nums[i] + nums[m-i-1])
        return ans

881. 救生艇（20250310更新）

Java

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        // 就是考虑最重的和最轻的组合
        // 如果小于等于limit就表示可以，如果大于limit就表示，最重的和任何一个人都没办法坐同一条船
        int ans = 0;
        Arrays.sort(people);
        int l = 0, r = people.length - 1;

        while (l <= r) {
            if (people[l] + people[r] <= limit) {
                l++;
            }
            r--;
            ans++;
        }
        return ans;
    }
}

Python

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        n = len(people)
        l, r = 0, n-1

        ans = 0
        while l <= r:
            if people[l] + people[r] <= limit:
                l += 1
                r -= 1
            else:
                r -= 1
            ans += 1
        return ans

2592. 最大化数组的伟大值（20250312更新）

先排序，就是遍历元素，找到第一个比它大的元素，（双指针）

Java

class Solution {
    public int maximizeGreatness(int[] nums) {
        // 田忌赛马
        Arrays.sort(nums);
        int i = 0;
        for (int x : nums) {
            if (x > nums[i]) {
                i++;
            }
        }
        return i;
    }
}

Python

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        i = 0
        for x in nums:
            if x > nums[i]:
                i += 1
        return i

2576. 求出最多标记下标（20250312）

题目的核心就是求 2 * nums[i] <= nums[j]，如果升序排序的话，那么i肯定小于j，我们想要的就是尽可能多的满足这个条件，所以当nums[i]比较小的时候，找到满足条件的最小的nums[j]，（nums[j]右侧的数也是满足的），这个思路没什么问题。

但是在做的时候，没办法实现定位到满足条件的最小下标。用(n+1) / 2 来定位。

Java

class Solution {
    public int maxNumOfMarkedIndices(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int i = 0;
        for (int x = (n + 1) / 2; x < n; x++) {
            if (nums[i] * 2 <= nums[x]) {
                i++;
            }
        }
        return i * 2;
    }
}

Python

class Solution:
    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        i = 0
        # 在这里x相当于有指针，i相当于左指针
        # 为什么要(n+1)//2上取整，因为如果n是奇数的话，中间那个数不参与匹配
        for x in nums[(n + 1) // 2 :]:
            if nums[i] * 2 <= x:
                i += 1
        return i * 2

2.3、双序列配对

2037. 使每位学生都有座位的最少移动次数（20250313更新）

Java

class Solution {
    public int minMovesToSeat(int[] seats, int[] students) {
        Arrays.sort(seats);
        Arrays.sort(students);

        int n = seats.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += Math.abs(seats[i] - students[i]);
        }
        return ans;
    }
}

Python

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        seats.sort()
        students.sort()

        n = len(seats)
        ans = 0
        for x, y in zip(seats, students):
            ans += abs(x - y)
        return ans

455. 分发饼干（20250313更新）

排序之后，开始想的是从0开始到最小的数组长度，一个g对应一个s，下标也一一对应，但是这个是错误的。

我们应该是找到比g[i]大的最小的s[j]的值，这样才能尽可能多的满足小孩。

Java

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int ans = 0;
        int i = 0, j = 0;
        while (i < g.length && j < s.length) {
            if (s[j] >= g[i]) {
                ans++;
                i++;
            }
            j++;
        }
        return ans;
    }
}

Python

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()

        i = 0
        j = 0
        ans = 0
        while i < len(g) and j < len(s):
            if s[j] >= g[i]:
                ans += 1
                i += 1
            j += 1
        return ans

870. 优势洗牌（20250312更新）

田忌赛马

Java

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        int n = nums2.length;
        Integer[] ids = new Integer[n];
        for (int i = 0; i < n; i++) {
            ids[i] = i;
        }
        //
        Arrays.sort(ids, (x, y) -> nums2[x] - nums2[y]);

        int left = 0, right = n - 1;
        int[] ans = new int[nums1.length];

        for (int x : nums1) {
            if (x > nums2[ids[left]]) {
                ans[ids[left]] = x;
                left++;
            } else {
                ans[ids[right]] = x;
                right--;
            }
        }
        return ans;
    }
}

Python

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:

        nums1.sort()
        n = len(nums2)
        # 把下标排序，排序逻辑用数组元素
        ids = sorted(range(n), key=lambda i: nums2[i])

        ans = [0] * n
        left, right = 0, n - 1
        for x in nums1:
            # 如果n1最小（下等马）的都大于n2的最小的（下等马），那么就得分
            # 否则就用n1最小的（下等马）比n2的最大的（上等马）
            if x > nums2[ids[left]]:  # 比下等马
                ans[ids[left]] = x
                left += 1
            else:  # 比上等马
                ans[ids[right]] = x
                right -= 1
        return ans

826. 安排工作以达到最大收益（20250314更新）

题目还是很容易理解的，主要是解决遇到的问题

• 到底是先遍历worker还是先遍历difficulty？ （遍历worker）
• 大于了不能直接取，还需要往后判断，取最大值，解决不了取到满足条件的最大的profit，就是当worker[i] = 6的时候，取不到最大的profit = 30（在循环里面使用while来实现获取最大的profit）

Java

class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = difficulty.length;
        int[][] jobs = new int[n][2];
        for (int i = 0; i < n; i++) {
            jobs[i][0] = difficulty[i];
            jobs[i][1] = profit[i];
        }

        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
        Arrays.sort(worker);

        int ans = 0;
        int maxProfit = 0;
        int j = 0;

        for (int w : worker) {
            while (j < jobs.length && jobs[j][0] <= w) {
                maxProfit = Math.max(maxProfit, jobs[j][1]);
                j++;
            }
            ans += maxProfit;
        }
        return ans;
    }
}

Python

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        # 还能这么玩
        jobs = sorted(zip(difficulty, profit))
        worker.sort()

        ans = 0  # 最后返回的最大利润
        max_frofit = 0  # worker[i] 的最大利润
        j = 0  # 指向difficulty的指针

        for w in worker:  # 遍历的worker
            while j < len(jobs) and jobs[j][0] <= w:  # jobs[j][0]表示工作难度
                max_frofit = max(max_frofit, jobs[j][1])
                j += 1
            ans += max_frofit
        return ans

2.4、从最左/最右开始贪心

对于无法排序的题目，尝试从左到右/从右到左贪心。思考第一个数/最后一个数的贪心策略，把n个数的原问题转换成n-1个数（或者更少）的字问题。

读者可以对比动态规划中线性DP、状态机DP的区别，思考什么情况下只能DP不能贪心，从而加深对局部最优和全局最优的理解。

3402. 使每一列严格递增的最少操作次数（20250314更新）

Java

class Solution {
  	// 灵神版
    public int minimumOperations(int[][] grid) {
        int ans = 0;
        for (int j = 0; j < grid[0].length; j++) {
            int pre = -1;
            for (int[] row : grid) {
                int x = row[j];
                ans += Math.max(pre + 1 - x, 0);
                pre = Math.max(pre + 1, x);
            }
        }
        return ans;
    }
}

Python

class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        ans = 0
        for i in range(n):
            for j in range(1, m):  # 从第二行开始
                if grid[j][i] > grid[j - 1][i]:  # 如果第j行大于j-1行就直接跳过
                    continue
                x = grid[j - 1][i] + 1 - grid[j][i]  # 计算需要的操作步骤
                grid[j][i] += x  # 将增加的添加到原数组上
                ans += x
        return ans

Python

class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        ans = 0
        for col in zip(*grid):  # 遍历每一列
            pre = -inf
            for x in col:
                ans += max(pre + 1 - x, 0)
                pre = max(pre + 1, x)
        return ans

3191. 使二进制数组全部等于 1 的最少操作次数 I（20250318更新）

Java

class Solution {
    public int minOperations(int[] nums) {
        int ans = 0;
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] == 0) {
                nums[i + 1] ^= 1;
                nums[i + 2] ^= 1;
                ans++;
            }
        }
        return nums[n - 2] == 1 && nums[n - 1] == 1 ? ans : -1;
    }
}

Python

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        # 从左到右模拟这个过程，最后判断最后两个数字是否是1
        ans = 0
        for i in range(len(nums) - 2):
            if nums[i] == 0:
                nums[i + 1] ^= 1
                nums[i + 2] ^= 1
                ans += 1
        return ans if nums[-2] and nums[-1] else -1

Changelog

Last Updated: View All Changelog

• 3d2e0-

  feat(wiki): algo: 算法总结

  On 3/30/25