贪心算法 - Greedy Algorithm

最近更新：2025-10-20 | 字数总计：2.4k | 阅读估时：9分钟 | 阅读量：次

基础算法 - 贪心算法
1. 贪心算法的应用
2. 相关题目

基础算法 - 贪心算法

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致全局最优解的算法。贪心算法在某些问题中能够产生全局最优解，而在另一些问题中只能产生近似解。

贪心算法的主要特点包括：

局部最优选择：每一步都选择当前状态下的局部最优解。
简单高效：相对于其他复杂算法，贪心算法通常更为简单且计算效率高。
不保证全局最优：贪心算法并不总能保证找到全局最优解，适用于某些特定类型的问题。

贪心算法的应用

贪心算法通常应用于以下类型的问题：

最小生成树：如 Kruskal 算法和 Prim 算法。
单源最短路径：如 Dijkstra 算法。
活动选择问题：选择最大数量的互不相交活动。
背包问题：在一定容量限制下选择物品使总价值最大（贪心算法仅适用于分数背包问题）。

相关题目

121. 买卖股票的最佳时机 - 力扣（LeetCode）

难度：简单

动态规划

想要获得最大收益，可以计算在第i天买入股票可以获得的最大收益的每一种可能，然后进行比较得出最小值。

在第i天买入股票可以获得的最大收益值 = 第i天之后的最高股价 - 第i天的股价。

可以用暴力的解法，两个for循环，时间复杂度为O(n^2^)。

将买入的钱固定下来，去寻找未知的卖出的钱，而卖出的钱就一直往后遍历就可以，这样其实每一次遍历都会有多余的操作，因为只要遍历一次j就可以知道某一个范围内最大的是多少了，而这样按照这种暴力的思想，会导致其重复计算。

那么，如何避免这个多余的遍历呢，我们可以用记忆化搜索的方式，或者说是动态规划的方法来记录。

核心思想就在：如果今日买入股票，获得的最高收益 = 之后股价最大值 - 今日股票值，而这个“之后股价最大值“由我们先遍历一次得出

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int len = prices.length;
        // dp[i]代表，第i天后股价最高值，i的取值为0....len-1
        int[] dp = new int[len];
        dp[len-1] = Integer.MIN_VALUE;
        for(int i=len-2;i>=0;i--){   // 从尾部开始向头部遍历
            dp[i] = Math.max(dp[i+1],prices[i+1]);
        }
        // System.out.println(Arrays.toString(dp));
        // 不在最后一天买股票
        for(int i=0;i<len-1;i++){
            ans = Math.max(dp[i] - prices[i],ans);
        }
        return ans;
    }
}

贪心

并不关心其他日子买入股票所获得的最大收益，只关注最大收益。

最大收益就是股票最高价 - 曾经的股票最低价

class Solution {
    public int maxProfit(int[] prices) {
         int res = 0;
         int min = Integer.MAX_VALUE;
         for(int n : prices){
             min = Math.min(min,n);
             res = Math.max(res,n - min);
         }
         return res;
    }
}

55. 跳跃游戏 - 力扣（LeetCode）

难度：中等

DFS

可以利用DFS 确保探索所有可能的路径，当找到成功成功路劲之后直接返回。

class Solution {
    boolean flag = false;
    public boolean canJump(int[] nums) {
        dfs(nums,0);
        return flag;
    }
    private void dfs(int[] nums,int cur){
        if(flag||cur>=nums.length){
            flag = true;
            return;
        }
        int val = nums[cur];
        for(int i=val;i>=1;i--){  // 运行超时的关键
            dfs(nums,cur+i);
            if(flag==true)return;
        }
    }
}

但是这种方法在数据特别大的情况下很容易运行超时，而且还容易栈溢出。

效率低下：DFS 在每个节点尝试所有可能的跳跃，导致时间复杂度较高，特别是在数组较大或跳跃次数较多的情况下，容易导致运行超时。

冗余计算：很多路径会被重复计算，导致性能问题。

贪心

class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        // max记录能到的最大位置
        int max = 0;
        // 遍历每一个元素，根据这个元素的值确定可到达的最大位置
        for(int i=0;i<len;i++){
            // 如果当前大于了 目前能到达的最大位置，表明已经寄了
            if(i>max)return false;
            // 更新max
            max = Math.max(max,nums[i]+i);
        }
        return true;
    }
}

具体来说，它体现了以下贪心策略：

局部最优选择：在每一步，选择当前能跳到的最远位置。这意味着每次都在尽可能扩展能到达的范围。
全局最优结果：通过每次选择当前能到达的最远位置，最终判断是否能够到达数组的末尾。

在代码中，max变量记录了当前能到达的最远位置。遍历数组时，max会不断更新为nums[i] + i和max中的最大值，这意味着在每一步，算法都选择能跳到的最远位置。

确保在每一步都选择当前最优的跳跃，从而判断是否能够跳到最后一个位置。

45. 跳跃游戏 II - 力扣（LeetCode）

难度：中等

与跳跃游戏比，这里给出的样例都可以满足抵达最后一个位置，但这个题求的是最小的跳跃次数。

DFS

class Solution {
    int res = Integer.MAX_VALUE;
    public int jump(int[] nums) {
        // 调用 dfs 时传递初始位置 0 和初始跳跃次数 0
        dfs(nums, 0, 0);
        return res;
    }

    private void dfs(int[] nums, int cur, int jumps) {
        // 如果当前下标超过或到达数组末尾，更新最小跳跃次数
        if (cur >= nums.length - 1) {
            res = Math.min(res, jumps);
            return;
        }

        int val = nums[cur];
        // 尝试从当前位置跳跃到所有可能的位置
        for (int i = 1; i <= val; i++) {
            dfs(nums, cur + i, jumps + 1);
        }
    }
}

遍历每一个成功路径，同时记录跳跃数，将最小跳跃数留下。

超时

动态规划

dp[i]代表跳到位置i需要的最少跳跃数。

对于位置 i，你可以跳 nums[i] 步。那么对于所有可以从 i 跳到的位置 i + j，更新 dp 数组的逻辑如下：

当前的位置：i
可以跳的步数：nums[i]
从当前位置 i 跳到所有可能的位置 i + j

1
2
3

for (int j = 1; j <= nums[i] && i + j < len; j++) {
    dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
}

完整代码如下：

class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        // dp[i]代表抵达第i个位置所需要的最小的跳跃数
        int[] dp = new int[len];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        int tmp;
        for(int i=0;i<len;i++){
            tmp = dp[i];
            // 更新dp数组
            for(int j=1;j<=nums[i]&&i+j<len;j++){
                dp[i+j] = Math.min(dp[i+j],dp[i]+1);
            }
        }
        return dp[len-1];
    }
}

这种方法是可以通过的，不过时间复杂度略高O(n*m)， m=Max(nums[i]),而本题中0<nums[i]<1000，所以最大也就1000而已，所以还是可以通过的，如果数字更大一点，这个方法就会超时了。

贪心

关注起跳的时机

class Solution {
    
    public int jump(int[] nums) {
        // 规定[left,right)为某一轮的起跳区间
        int left = 0;
        int right = 1; // 初始时候只能从0位置起跳
        int maxPos = 0; // 表示每一轮起跳所能抵达的最大位置
        int count = 0; // 表示用了多少轮（起跳次数）
        
        // 继续跳跃直到能够到达数组的最后一个位置
        while(maxPos < nums.length - 1){
            // 在当前起跳区间[left, right)内寻找最远能到达的位置
            for(int i = left; i < right; i++){
                // 更新每个位置能跳到的最远位置
                maxPos = Math.max(maxPos, i + nums[i]);
            }
            count++; // 增加跳跃次数
            // 更新起跳区间
            left = right;
            right = maxPos + 1;
        }
        return count; // 返回跳跃次数
    }
}

贪心策略的体现：

每次从当前起跳区间内，选择能跳到的最远位置进行更新。
通过这种方式，每次跳跃都是在当前能够选择的最优位置，从而保证跳跃次数最少。

只关注最少起跳次数，并不关心最少起跳次数的路径。

763. 划分字母区间 - 力扣（LeetCode）

难度：中等

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();
        int len = s.length();
        // 记录每一个字符出现的最后的一个位置
        int[] last = new int[26];
        char tmp;
        for(int i=0;i<len;i++){
            tmp = s.charAt(i);
            last[tmp-'a'] = i;
        }
        // 划分区间 [start,end]
        int start = 0;
        int end = 0;
        int cur = 0;
        while(cur<len){
            tmp = s.charAt(cur);
            // end代表，在[start,cur]这个区间中的某一个字符，出现的最远的位置
            // 即[start,end]才是一个合格的区间
            end = Math.max(end,last[tmp-'a']);
            // 当cur==end之后，证明[start,end]是一个合格的区间了
            if(cur==end){
                res.add(end-start+1);
                // 需要重新定start了
                start = end+1;
            }
            cur++;
        }
        return res;
    }
}

通过这种方式，每次都选择一个尽可能大的区间，使得区间内的字符在该区间之外不再出现。

当遍历到的位置 cur 等于当前区间的终点 end 时，说明当前区间 [start, end] 已经确定，即[start,end]中所有的字串不会出现在其他区间中。并且这样还做到了将字符串划分为尽可能多的片段。

2024-06-15 该篇文章被 jay1an 打上标签: 基础算法贪心算法归为分类: 基础算法