LeetCode-17day:贪心算法

贪心算法经典题目总结（C++实现）

贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的算法。本文总结了四道经典的贪心算法问题，帮助你更好地理解和掌握贪心算法的应用。

🟢 1. 买卖股票的最佳时机（Best Time to Buy and Sell Stock）

📄 题目描述：

给定一个数组 prices，其中第 i 个元素是第 i 天的股票价格。假设你最多只能进行一次交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

🧠 解题思路（简洁版）

• 一次遍历：
  • 遍历价格数组，维护当前最低价格 minp 和最大利润 maxp。
  • 每天更新最低价格和最大利润。

⏱️ 复杂度分析

• 时间复杂度：O(n)，其中 n 为价格数组长度。
• 空间复杂度：O(1)。

✅ C++ 实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minp = 1e9, maxp = 0;
        for (auto& price : prices) {
            maxp = max(maxp, price - minp);
            minp = min(minp, price);
        }
        return maxp;
    }
};

🟢 2. 跳跃游戏（Jump Game）

📄 题目描述：

给定一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

🧠 解题思路（简洁版）

• 贪心算法：
  • 遍历数组，维护当前能到达的最远位置 rightmost。
  • 若当前位置可达，则更新最远位置。
  • 若最远位置覆盖数组末尾，返回 true。

⏱️ 复杂度分析

• 时间复杂度：O(n)，其中 n 为数组长度。
• 空间复杂度：O(1)。

✅ C++ 实现

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int rightmost = 0;
        for (int i = 0; i < n; i++) {
            if (i <= rightmost) {
                rightmost = max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) return true;
            }
        }
        return false;
    }
};

🟢 3. 跳跃游戏 II（Jump Game II）

📄 题目描述：

给定一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

🧠 解题思路（简洁版）

• 贪心算法：
  • 遍历数组，维护当前能到达的最远位置 maxpos 和当前步的边界 end。
  • 若当前位置到达边界，则更新边界为最远位置并增加步数。
  • 直到覆盖数组末尾。

⏱️ 复杂度分析

• 时间复杂度：O(n)，其中 n 为数组长度。
• 空间复杂度：O(1)。

✅ C++ 实现

class Solution {
public:
    int jump(vector<int>& nums) {
        int maxpos = 0, n = nums.size(), end = 0, step = 0;
        for (int i = 0; i < n - 1; i++) {
            if (maxpos >= i) {
                maxpos = max(maxpos, i + nums[i]);
                if (i == end) {
                    end = maxpos;
                    step++;
                }
            }
        }
        return step;
    }
};

🟢 4. 划分字母区间（Partition Labels）

📄 题目描述：

给定一个字符串 s，将字符串划分成若干个字母区间，每个区间内的字母互不相同。返回每个区间的长度。

🧠 解题思路（简洁版）

• 贪心算法：
  • 预处理每个字符的最后出现位置。
  • 遍历字符串，维护当前区间的起始和结束位置。
  • 当遍历到当前区间的结束位置时，记录区间长度并更新起始位置。

⏱️ 复杂度分析

• 时间复杂度：O(n)，其中 n 为字符串长度。
• 空间复杂度：O(1)，固定大小的数组。

✅ C++ 实现

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26];
        int length = s.size();
        for (int i = 0; i < length; i++) {
            last[s[i] - 'a'] = i;
        }

        vector<int> partition;
        int start = 0, end = 0;
        for (int i = 0; i < length; i++) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) {
                partition.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return partition;
    }
};

📌 总结

希望本文对你有所帮助！如果你还有其他问题，欢迎继续提问。