学网站建设工作,注册网络平台怎么注册,wordpress 官方主题,系统门户文章来源#xff1a; https://blog.csdn.net/weixin_45630258/article/details/132737088 欢迎各位大佬指点、三连
1、题目#xff1a;
给定一个整数数组 nums#xff0c;找出给定数组中两个数字之间的最大差值。要求#xff0c;第二个数字必须大于第一个数字。 2、分析特…文章来源 https://blog.csdn.net/weixin_45630258/article/details/132737088 欢迎各位大佬指点、三连
1、题目
给定一个整数数组 nums找出给定数组中两个数字之间的最大差值。要求第二个数字必须大于第一个数字。 2、分析特点
求最大差值 最大值 - 最小值只需要遍历价格数组一遍记录历史最小值非最小值的考虑是最大值。 3、代码 4、复杂度分析 时间复杂度O(n)只需要遍历一次。空间复杂度O(1)只使用了常数个变量。 5、总结
使用打擂台的思想遍历的时候考虑当前值是最小值则记录最小值否则考虑当前值是最大值进行更新。 6、其他解法–暴力法 6-1、复杂度分析 7、题目变化
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。 我们来假设自己来购买股票。随着时间的推移每天我们都可以选择出售股票与否。那么假设在第 i 天如果我们要在今天卖股票那么我们能赚多少钱呢 显然如果我们真的在买卖股票我们肯定会想如果我是在历史最低点买的股票就好了太好了在题目中我们只要用一个变量记录一个历史最低价格 minprice我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。 因此我们只需要遍历价格数组一遍记录历史最低点然后在每一天考虑这么一个问题如果我是在历史最低点买进的那么我今天卖出能赚多少钱当考虑完所有天数之时我们就得到了最好的答案。 7-1、一次遍历 public int maxProfit(int prices[]) {int minprice Integer.MAX_VALUE;int maxprofit 0;for (int i 0; i prices.length; i) {if (prices[i] minprice) {minprice prices[i];} else if (prices[i] - minprice maxprofit) {maxprofit prices[i] - minprice;}}return maxprofit;}■ 复杂度分析 时间复杂度O(n)只需要遍历一次。空间复杂度O(1)只使用了常数个变量。 7-2、暴力法
public class Solution {public int maxProfit(int[] prices) {int maxprofit 0;for (int i 0; i prices.length - 1; i) {for (int j i 1; j prices.length; j) {int profit prices[j] - prices[i];if (profit maxprofit) {maxprofit profit;}}}return maxprofit;}
}■ 复杂度分析 如果本文对你有帮助的话记得给一乐点个赞哦感谢
