121 买卖股票的最佳时机

题目

给定一个数组 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。

• 法一：贪心，分别找到价格最低和最高的一天，注意最低要在最高之前

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit=0;//记录利益
        int cur_min=prices[0];//记录当前的最小价格
        for(int i=0;i<prices.size();i++)
        {
            profit=max(profit,prices[i]-cur_min);//最大利益
            cur_min=min(cur_min,prices[i]);//更新最小价格
        }
        return profit;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

• 时间复杂度O(n)
• 空间复杂度O(1)
• 思路
  • 在最低处买入，最高处卖出，最低要在最高前
  • 记录当前的最低处，对每一个元素计算当前价格与最低处的差值，如果大于当前最大利益就更新。然后比较当前价格与最小价格，如果小于就更新最小价格。注意如果更新了最小价格，此时计算最大利益必然是0，是不会大于当前最大利益的，故先判断是否要更新最大利益，再判断是否要更新最小价格