营销型网站建设实训总结,国外最牛设计网站,百度手机导航官方新版,wordpress健身模版文章目录题目描述代码 思路初版代码更新啦#xff5e;优化代码再次更新题目描述
讲道理#xff0c;一眼dp
代码 思路
时间复杂度O(n)#xff0c;不过可改进的地方还多#xff0c;跑出来大概6ms。
初版代码
class Solution {public int maxProfit(int[] p…
文章目录题目描述代码 思路初版代码更新啦优化代码再次更新题目描述
讲道理一眼dp
代码 思路
时间复杂度O(n)不过可改进的地方还多跑出来大概6ms。
初版代码
class Solution {public int maxProfit(int[] prices) {// 做啥找一个i,jj i)且prices[j] prices[i]使得 max prices[j] - prices[i]// 用dp做吧int len prices.length;if(len 1){return 0;}// dp[i]代表当前值之后能遇到的最大值int[] dp new int[len];dp[len-1] 0;for(int ilen-2;i 0;i--){dp[i] Math.max(prices[i1],dp[i1]);}int max 0;for(int i0;ilen-1;i){max Math.max(dp[i] - prices[i],max);}return max;}
}更新啦优化代码
节约了空间空间复杂度由 O(n) 变成了 O(1)
class Solution {public int maxProfit(int[] prices) {if(prices.length 2) {return 0;}int len prices.length;int max prices[len - 1];int ans 0;for(int i len - 2; i 0; i--) {int nowProfit max - prices[i];// ans 更新if(nowProfit ans) {ans nowProfit;}// min 更新if(prices[i] max) {max prices[i];} }return ans;}
}再次更新
class Solution {public int maxProfit(int[] prices) {int max prices[prices.length - 1];int res 0;for(int i prices.length - 2; i 0; i--) {max Math.max(max, prices[i 1]);res Math.max(max - prices[i], res);}return res;}
}
