LeetCode 121 Best Time to Buy and Sell Stock

标签: 股票问题 LeetCode 发布于:2022-02-03 23:14:17 编辑于:2022-02-05 16:53:22 浏览量:389

题目分析

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

暴力遍历法

遍历所有买卖可能,O(n^2) 时间复杂度。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 0; i < prices.size(); i++) {
            for (int j = i + 1; j < prices.size(); j++) {
                ans = max(ans, prices[j] - prices[i]);
            }
        }
        return ans;
    }
};

TLE 了。

只遍历出售价格

我们遍历所有价格,使其轮流作为出售价格。 对于每一个出售价格,其最佳的买入价格即其之前最低的那个价格,因此我们完全可以 one pass 解决问题。

时间复杂度 O(n)。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        int buy = prices[0];
        for(int i = 1; i < prices.size(); i++) {
            // calculate profit based on current sell price
            ans = max(ans, prices[i] - buy);
            // update new lower buy price
            buy = min(buy, prices[i]);
        }
        return ans;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/