贪心算法经典例题及代码

贪心算法是一种常用的算法思想，其主要思路是在每一步操作中都尽可能地采取最优的选择，以期得到全局最优解。贪心算法既适用于离线问题，也适用于在线问题。在本文中，我将给出贪心算法的经典例题及代码，并从多个角度进行分析。

例题1：跳跃游戏

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

例如：

输入: nums = [2,3,1,1,4]

输出: true

解释: 跳到最后一个位置的方法如下：从下标 0 跳 1 步到下标 1, 然后跳 3 步到最后一个位置。

贪心算法思路：

遍历数组，记录每一个位置能够跳到的最远距离，并实时更新这个最远距离。

如果当前位置超过了最远距离，说明无法到达当前位置，直接返回false。

如果最后一个位置在最远距离内，说明可以到达最后一个位置，返回true。

代码实现：

bool canJump(vector & nums) {

int n = nums.size();

int max_jump = 0;

for (int i = 0; i < n; i++) {

if (i > max_jump) {

return false;

}

max_jump = max(max_jump, i + nums[i]);

if (max_jump >= n - 1) {

return true;

}

}

return false;

}

时间复杂度：O(n)

空间复杂度：O(1)

例题2：买卖股票的最佳时机

给定一个数组prices，它的第i个元素prices[i]代表一支给定股票第i天的价格。

你只能选择在某一天买入这只股票，并在未来的某一个不同的日子卖出该股票。计算你所能获得的最大利润。注意：你不能在买入股票前卖出股票。

例如：

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第2天（股票价格 = 1）的时候买入，在第5天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5。

贪心算法思路：

遍历数组，记录到当前位置为止的最低价格，计算当前价格与最低价格的差值，并与当前的最大利润进行比较，更新最大利润即可。

代码实现：

int maxProfit(vector & prices) {

int n = prices.size();

int min_price = INT_MAX;

int max_profit = 0;

for (int i = 0; i < n; i++) {

min_price = min(min_price, prices[i]);

max_profit = max(max_profit, prices[i] - min_price);

}

return max_profit;

}

时间复杂度：O(n)

空间复杂度：O(1)

从时间和空间复杂度分析，可以看出贪心算法具有良好的时间和空间性能，适用于大数据的处理。

此外，贪心算法还具有以下特点：

1. 贪心算法通常比动态规划算法更简单，更容易实现，但并不是所有问题都适用于贪心思想，需要具体问题具体分析。

2. 贪心算法不考虑后效性，只关注当前的最优选择，因此无法保证得到全局最优解，只能得到局部最优解。

3. 贪心算法一般需要证明贪心选择性质和最优子结构性质，并能够通过局部最优解来推导出全局最优解。

综上所述，贪心算法是一种基于局部最优选择的算法思想，具有良好的时间和空间性能。在使用贪心算法时，需要具体问题具体分析，并证明贪心选择性质和最优子结构性质。