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 sizeint 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 ansint ans = 0;for(int i=1;i<n;i++){// 这里小细节注意数组具体含义ans = max(ans, sufMax[i] - preMin[i]);}return ans;}
};

1.4 学习题解反思

我的解法时间复杂度O(n), 空间复杂度O(n)

题解中一次遍历完成，又是学到了的一天

有点类型经典的打导弹那题
一次遍历，每次记录下当前的最小股价和当前最大利润，
如果遇到最小股价即可更新，为什么可以更新？因为再往后遍历的高股价，是满足买这之前的所有的股价，所以选择更新最低的股价就行

2.4 bug日记

注意下标

2. 后记

仅分享自己的想法，有意见和指点非常感谢