讨论/《春招冲刺班 - 7 天刷题挑战》 - 121. 买卖股票的最佳时机/
《春招冲刺班 - 7 天刷题挑战》 - 121. 买卖股票的最佳时机
共 5 个回复

C++,动态规划,
执行用时:136 ms, 在所有 C++ 提交中击败了 50.69% 的用户。
内存消耗:94.9 MB, 在所有 C++ 提交中击败了7.49%的用户。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;

        int minprice = prices[0];
        vector<int> dp (n, 0);  // 用一维动态规划,dp[i] 表示前 i 天的最大利润

        // 动态规划主要部分
        for (int i = 1; i < n; ++i) {
            minprice = min(minprice, prices[i]);
            dp[i] = max(dp[i - 1], prices[i] - minprice);
        }
        return dp[n - 1];
    }
};
class Solution {
    public int maxProfit(int[] prices) {
        //记录之前的最小值
        int min = prices[0];
        //返回值
        int res = 0;
        for(int i = 1; i < prices.length; i++) {
            min = Math.min(min,prices[i]);
            res = Math.max(res,prices[i] - min);
        }
        
    }
}

遍历一遍数组,用minValue来记录当前最小值,然后用当前值减去最小值进行比较更新,再更新最小值。
代码如下:

import java.lang.Math;
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1)
            return 0;
        int minValue = prices[0];
        int res = 0;
        for(int i = 1; i<prices.length; i++){
            res = Math.max(res, prices[i] - minValue);
            minValue = Math.min(minValue, prices[i]);
        }
        return res;
    }
}

遍历一遍,记录到当前位置的最小值为买入点,同时判断如果当前卖出可得的获利

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int m = prices[0];
        int r = 0;
        for(const auto& it:prices)
        {
            if(it < m)
            {
                m = it;
            }
            else if(it - m > r)
            {
                r = it - m;
            }
        }
        return r;
    }
};

参与“7天刷题挑战”的童鞋欢迎点击问卷加入专属社群哦~
2月1日-7日,字节跳动工程师直播刷题等你来围观