Leetcode 高频面试题 股票交易问题详解

一. 只能买一次，卖一次 （Leetcode 121）

这是最简单的情况，最低点买入，最高点卖出就行。

class Solution {
public:int maxProfit(vector& prices) {// 最低点买，最高点卖if(prices.size()==0) return 0;int profit = 0, buyPrice = prices[0];for(auto price:prices){profit = max(profit,price-buyPrice);buyPrice = min(buyPrice,price);}return profit;}
};

二. 无限次买，无限次卖  （Leetcode 122）

valley买，peak卖。等效于所有涨的利润都获得，卖的忽略。

class Solution {
public:int maxProfit(vector& prices) {int profit = 0, n = prices.size();for(int i=0;i0) profit+=(prices[i+1]-prices[i]);}return profit;}
};

三. 无限次买，无限次卖，含1天冷冻期 （Leetcode 309）

有冷冻期只能用动态规划处理

第i天持股的最大利润 dp[i][0];

第i天不持股处于冷冻期的最大利润 dp[i][1];

第i天不持股不处于冷冻期的最大利润 dp[i][2];

dp[i][0] = max(dp[i-1][0],dp[i-1][2]-prices[i]);

dp[i][1] = dp[i-1][0]+prices[i];

dp[i][2] = max(dp[i-1][2],dp[i-1][1]);

这里dp转移充分利用了冷冻期为1天的特殊性，持股后卖出，就会进入到冷冻期。

class Solution {
public:int maxProfit(vector& prices) {int n = prices.size();if(n==0) return 0;vector> dp(n,vector(3));dp[0][0] = -prices[0];for(int i=1;i

class Solution {
public:int maxProfit(vector& prices) {int n = prices.size();if(n==0) return 0;vector> dp(n,vector(3));dp[0][0] = -prices[0];for(int i=1;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！