怎么验证网站备案密码是否正确,前端培训学校,wordpress wpsyntax,建设三类人员报考网站LeetCode: 121. 买卖股票的最佳时机
121. 买卖股票的最佳时机 - 力扣#xff08;LeetCode#xff09;
1.思路
暴力解法、贪心也算比较符合思维#xff0c;动规不容易想到#xff0c;且状态处理不易处理 股票每天的状态为持有或不持有#xff1a;声明dp数组#xff1a…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}
191// 暴力解法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}
203.时间复杂度
时间复杂度O(n). 空间复杂度O(1).
