7.买卖股票的时机

PS: 搜题的自己加上"最佳"两字

一、题目

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

二、示例

示例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。

三、代码实现

public static int maxProfit(int[] prices){int max = 0,min = 0,price = 0;min = prices[0];if (prices.length < 2){return 0;}for (int i = 0,j = 1;i < prices.length;i++){if (min > prices[i]){min = prices[i];}if (max < prices[j]){max = prices[j];}if (j+1 < prices.length){j++;}if ((max - min) > price){price = max - min;}max = 0;}return price;}

运行是运行得了,就是比较慢
还有就是代码有点冗余
对我来说,想出来就已经烧掉不少脑细胞了,懒得优化了

官方解①：暴力破解

 public static int maxProfitByViolence(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;}

无往不利的暴力破解也有摔跟头的时候
几行代码看似很有大佬的风范,运行起来时间却超过限制-----运行器的数组给得贼长

官方解②: 一次遍历

public static int maxProfitOptimize(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;
}

真正学到了,我还是没跳出传统思维
如果程序走进minPrice = prices[i]，那么prices就不会被当作最大值,我的代码还要把这个数当成最大值再走一遍
而且也没有设立一个多余的变量price
从结果上看,这套解比我那个时间上空间上都优化了不少

四、复杂度分析

官方解①：暴力破解

• 时间复杂度: O(n²)
• 空间复杂度: O(1)

官方解②：一次遍历

• 时间复杂度: O(n)
• 空间复杂度: O(1)

注:能不用两层循环就别用两层循环

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！