原题链接🔗:买卖股票的最佳时机
难度:简单⭐️
题目
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
示例 1:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:
输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。
提示:
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 104
贪心算法
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法策略。它在有最优子结构的问题中尤为有效,即局部最优解能决定全局最优解的问题。
贪心算法不保证会得到最优解,但在某些问题上贪心算法的解是足够好的,或者至少是可行的。它的优点是简单、高效,但缺点是可能不会得到最优解。
贪心算法通常用于以下问题:
- 资源分配问题:如任务调度、内存分配等。
- 最优搜索问题:如霍夫曼编码树的构造。
- 图论问题:如最小生成树的构造(Prim算法和Kruskal算法)。
贪心算法的实现通常遵循以下步骤:
- 定义一个贪心选择函数:该函数用于选择当前最优的选择。
- 定义一个备忘录结构:用于记录已经作出的选择。
- 作出贪心选择:根据贪心选择函数和备忘录结构,选择当前的最优解。
- 更新备忘录:将选择的结果记录在备忘录中。
- 判断是否达到目标:如果达到目标,则结束算法。
贪心算法的关键是贪心选择条件,它必须满足两个条件:
- 局部最优:在每一步选择当前的最优解。
- 全局最优:通过局部最优选择能够达到全局最优解。
如果问题具有贪心选择性质,即局部最优解能导致全局最优解,那么贪心算法是可行的。然而,如果问题不具有这种性质,贪心算法可能只能找到一个近似解。
题解
- 解题思路:
LeetCode 上的 “买卖股票的最佳时机” 是一道非常经典的算法题目,主要考察的是贪心算法的思想。这个问题的描述是这样的:给定一个数组,每个元素代表在第 i 天的股票价格,如果那一天你买入股票,然后第二天卖出股票,求出最大利润。你可以假设你最多只能完成一笔交易(即买入和卖出一股)。
解题思路如下:
理解问题:首先明确题目要求,即在一个给定的价格数组中找到一次买入和一次卖出的时机,使得利润最大化。
贪心算法:贪心算法在这个问题中的应用是,每天我们都会检查当前价格是否比之前所有天的价格都低,如果是,则记录为买入价格。同时,我们也会计算如果今天卖出的利润,并更新最大利润。
遍历数组:使用一次遍历,从左到右检查数组中的每个价格。
维护两个变量:一个用于记录迄今为止的最低价格
min_price
,另一个用于记录迄今为止的最大利润max_profit
。更新逻辑:
- 如果当前价格小于
min_price
,则更新min_price
为当前价格。- 如果当前价格减去
min_price
大于max_profit
,则更新max_profit
。
- c++ demo:
#include <iostream>
#include <vector>
#include <algorithm> // 用于std::min和std::max// 函数声明
int maxProfit(const std::vector<int>& prices);int main() {// 测试用例std::vector<int> prices1 = { 7, 1, 5, 3, 6, 4 };std::vector<int> prices2 = { 7, 6, 4, 3, 1 };std::vector<int> prices3 = {};// 调用函数并打印结果std::cout << "Max profit for prices1: " << maxProfit(prices1) << std::endl;std::cout << "Max profit for prices2: " << maxProfit(prices2) << std::endl;std::cout << "Max profit for prices3: " << maxProfit(prices3) << std::endl;return 0;
}// 函数定义
int maxProfit(const std::vector<int>& prices) {if (prices.empty()) return 0;int min_price = std::numeric_limits<int>::max();int max_profit = 0;for (int price : prices) {if (price < min_price) {min_price = price;}else if ((price - min_price) > max_profit) {max_profit = price - min_price;}}return max_profit;
}
- 输出结果:
Max profit for prices1: 5
Max profit for prices2: 0
Max profit for prices3: 0
- 代码仓库地址: maxProfit