Best Time to Buy and Sell Stock

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 460 | 阅读时间 ≈ 2

题目描述

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

题目解法

一看题目觉得还是挺简单的，可以用最简单的穷举法

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

Runtime: 828 ms, faster than 8.10% of C++ online submissions for Best Time to Buy and Sell Stock.
Memory Usage: 9.6 MB, less than 14.91% of C++ online submissions for Best Time to Buy and Sell Stock.

但是结果并不是很理想，时间用的太多了。有两个循环时间复杂读为O(n^2)

优化方法

看评论有一种方法，其实只用记录之前都最小值和最大利润即可。如果当前值小于最小值就更新最小值，否则计算当前值与最小值都差值是不是大于最大利润。

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

Runtime: 8 ms, faster than 78.13% of C++ online submissions for Best Time to Buy and Sell Stock.
Memory Usage: 9.5 MB, less than 60.83% of C++ online submissions for Best Time to Buy and Sell Stock.

速度一下就快了很多～