leetcode——买卖股票的最佳时机_leetcode买卖股票最佳时机

题目：
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

思路：

1. 暴力解决，查找每个元素之后的最大利润差对应的元素
2. 单次遍历，查找当前价格减去目前遇到的最小价格price-minprice

代码1：暴力（超出时间限制）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max=0;
        for(int i=0;i<prices.size();i++)
            for(int j=i;j<prices.size();j++)
                if(prices[j]-prices[i]>max)
                    max=prices[j]-prices[i];
        return max;
    }
};
1
2
3
4
5
6
7
8
9
10
11

代码2：（单次遍历）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minprice = 99999, maxprofit = 0;
        for (int price: prices) {
            minprice = min(price, minprice); //找目前遍历的最小值
            maxprofit = max(maxprofit, price - minprice); //获取目前利润差最大值
        }
        return maxprofit;
    }
};
1
2
3
4
5
6
7
8
9
10
11