让别人做网站多久开始注册域名,我为群众办实事工作总结,做的比较好的电商网站,网站app开发建设121. 买卖股票的最佳时机
难度#xff1a;简单
题目
给定一个数组 prices #xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获…121. 买卖股票的最佳时机
难度简单
题目
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。
示例 1
输入[7,1,5,3,6,4]
输出5
解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。示例 2
输入prices [7,6,4,3,1]
输出0
解释在这种情况下, 没有交易完成, 所以最大利润为 0。提示
1 prices.length 10^50 prices[i] 10^4
个人题解
方法一模拟
思路遍历数组记录当前最小值且每次比最小值小时都重置最大值因为大的值只能在最小值的右边找比较最大最小值的差值当大于前面记录的最大差值时才替换当前最大差值这个最大差值即最后要返回的结果
class Solution {public int maxProfit(int[] prices) {int min Integer.MAX_VALUE;int max -1;int result 0;for (int i 0; i prices.length; i) {if (prices[i] min) {min prices[i];max -1;} else if (prices[i] max) {max prices[i];result Math.max(max - min, result);}}return result;}
}复杂度分析
时间复杂度O(n)空间复杂度O(1)
官方题解
我们需要找出给定数组中两个数字之间的最大差值即最大利润。此外第二个数字卖出价格必须大于第一个数字买入价格。
形式上对于每组 i 和 j 其中 i j我们需要找出 max(prices[j] - prices[i])
方法一暴力法【超时】
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;}
}复杂度分析
时间复杂度O(n^2)空间复杂度O(1)
方法二一次遍历
public class Solution {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)
作者力扣官方题解 链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solutions/136684/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
