力扣日记121-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣日记121。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 题目

LeetCode 121 买卖股票的最佳时机

1.1 题意

给定每天股价，选择一天买入一天卖出，时间上满足先后顺序，求最大利润

1.2 分析

时间复杂度在O(n)

1 <= prices.length <= 10e5

简单想到对于某个位置找前面出现的最小值和后面出现的最大值，然后做差。
对于每个位置每次查找时间复杂度上O(n^2)，可以先查找，用数组记录下，然后

1.3 我的解法

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // get size
        int n = prices.size();
        // store pre min and suffex max
        // 细节开大两个位置，避免越界检查
        vector<int> preMin(n+2, INT_MAX);
        vector<int> sufMax(n+2, INT_MIN);
        for(int i=1; i<=n; i++){
            preMin[i] = min(preMin[i-1], prices[i-1]);
            // sufMax 实际是逆序，分两个循环写可以更好满足时空局部性，性能会更好
            // 这里偷懒写一块了就
            sufMax[n+1-i] = max(sufMax[n+2-i], prices[n-i]);
        }
        // fins ans
        int ans = 0;
        for(int i=1;i<n;i++){
            // 这里小细节注意数组具体含义
            ans = max(ans, sufMax[i] - preMin[i]);
        }
        return ans;
    }
};