leetcode_121 买卖股票的最佳时期
1. 题意
有一个股价变化图,你可以在一天买入,在未来一天卖出。
求通过这样一次操作的最大获利。
2. 题解
2.1 枚举
直接枚举,买入卖出的时间,肯定会超时啦~
时间复杂度为O(n2)O(n^2)O(n2)
空间复杂度为O(1)O(1)O(1)
class Solution {
public:int maxProfit(vector<int>& prices) {int ans = 0;int n = prices.size();for (int i = 0;i < n;++i) {for(int j = i + 1;j < n; ++j) {ans = max(ans, prices[j] - prices[i]);}}return ans;}
};
2.2 贪心
我们不难想到,我们每次卖股票的时候,只需要买入当前股票之前最低股份的股票就可以了!因此我们可以边统计最低股价,一边计算差值的最大值。
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int ans = 0;int mn = prices[0];for (int i = 1; i < n; ++i) {ans = max(prices[i] - mn, ans);mn = min(mn, prices[i]);}return ans;}
};
2.3 动态规划
动态规划的思路和贪心的感觉差不多,也不知道这算不算动态规划~
我们用dp[i]dp[i]dp[i]表示卖出的股票是prices[i]prices[i]prices[i]时的最大差值。
因此ans=max{dp[i]∣1≤i≤prices.size()−1}ans=\max \left\{dp[i]\ \Big |\ 1\le i \le prices.size()-1 \right\}ans=max{dp[i] 1≤i≤prices.size()−1}。
同样对于dp[i]dp[i]dp[i],我们需要知道iii之前的最小股份,所以最终代码跟
贪心差不多?空间优化完后,代码估计就跟贪心一样,就不写了。
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int ans = 0;vector<int> dp(n + 1, 0);int mn = prices[0];for (int i = 0;i < n; ++i) {dp[i + 1] = max( dp[i], prices[i] - mn);mn = min( prices[i], mn);}return dp[n];}
};
2.4 差分+动态规划
这个题目跟lc53 最大子数组和, 是相互变形的关系。
其实也就是差分和前缀和的关系。
lc53可以通过前缀和转换成这个问题,当然这个问题也可以通过差分变成
最大子数组和。贴个代码吧,也懒得再解释了OvO
class Solution {
public:int maxProfit(vector<int>& prices) {adjacent_difference( prices.begin(), prices.end(), prices.begin());prices[0] = 0;int ans = 0;int pre = 0;for (auto v: prices) {pre += v;ans = max( pre, ans);if (pre < 0)pre = 0;}return ans;}
};