算法练习Day49|● 121. 买卖股票的最佳时机 ● 122.买卖股票的最佳时机II
LeetCode: 121. 买卖股票的最佳时机
121. 买卖股票的最佳时机 - 力扣(LeetCode)
1.思路
暴力解法、贪心也算比较符合思维,动规不容易想到,且状态处理不易处理
股票每天的状态为持有或不持有:声明dp数组:int[][] dp = new int[prices.length][2];
确定含义:dp[i][0] 表示第i天持有股票的最大收益,dp[i][1] 表示第i天不持有股票的最大收益。
初始化:dp[0][0] = -prices[0];dp[0][1] = 0;
2.代码实现
1// 动规2class Solution {3 public int maxProfit(int[] prices) {4 if (prices.length == 0 || prices == null) {5 return 0;6 }7 // dp[i][0] 表示第i天持有股票的最大收益8 // dp[i][1] 表示第i天不持有股票的最大收益9 int[][] dp = new int[prices.length][2];
10 dp[0][0] = -prices[0];
11 dp[0][1] = 0;
12 for (int i = 1; i < prices.length; i++) {
13 dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
14 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
15 }
16 return dp[prices.length - 1][1];
17 }
18}
19
1// 暴力解法2class Solution {3 public int maxProfit(int[] prices) {4 int profit = 0;5 for (int i = 0; i < prices.length; i++) {6 for (int j = i + 1; j < prices.length; j++) {7 profit = Math.max(profit, prices[j] - prices[i]);8 }9 }
10 return profit;
11 }
12}
13// 贪心算法
14class Solution {
15 public int maxProfit(int[] prices) {
16 int low = Integer.MAX_VALUE;
17 int res = 0;
18 for (int i = 0; i < prices.length; i++) {
19 low = Math.min(prices[i], low);
20 res = Math.max(prices[i] - low, res);
21 }
22 return res;
23 }
24}
3.时间复杂度
时间复杂度:O(n).
空间复杂度:O(1).
LeetCode: 122.买卖股票的最佳时机II
122. 买卖股票的最佳时机 II - 力扣(LeetCode)
1.思路
动规真香,可以一个套路解决多题
和上一题类似,每天股票有两种状态,持有或不持有。
递推公式:
第i天持有,有两种情况:①第i-1天就持有;②第i天买入持有;
第i天不持有,有两种情况:①第i-1天就不持有;②第i天卖出,说明第i-1天持有(包含了当天买入卖出)
2.代码实现
1class Solution {2 public int maxProfit(int[] prices) {3 if (prices.length == 0 || prices == null) {4 return 0;5 }6 int[][] dp = new int[prices.length][2];7 // 8 // 9 dp[0][0] = -prices[0];
10 dp[0][1] = 0;
11 for (int i = 1; i < prices.length; i++) {
12 // 第 i 天持有股票:①当天买入且前一天不持有;②前一天持有
13 dp[i][0] = Math.max(dp[i - 1][1] - prices[i], dp[i - 1][0]);
14 // 第 i 天不持有股票:①第 i 天卖出;②第i-1天就不持有
15 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
16 }
17 return dp[prices.length - 1][1];
18 }
19}
20
3.时间复杂度
时间复杂度:O(n).
空间复杂度:O(1).