LeetCode121_121. 买卖股票的最佳时机

LeetCode121_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 <= 105
0 <= prices[i] <= 104

二、题解

方法：

题意： 合适的时间点买卖股票使得收益最大，最多只能买卖一次。

思路：

1、依次找出每个数与后面数的差值的最大值，放到一个list中。
2、再找到这个list中的最大值返回即可。

    //AC 没有看到击败率。。。可能是因为算法复杂度太高了。。。//200 / 200 test cases passed.	Status: Accepted	Runtime: 522 ms//这种解法2018年可以在英文版本提交通过，2023年1月在中文版本提交不通过。显示超时。public int maxProfit(int[] prices) {int res = 0;if (prices.length == 0) {return 0;}List<Integer> list = new ArrayList<Integer>();for (int i = 0; i < prices.length; i++) {int max = 0;for (int j = i; j < prices.length; j++) {//方法一：if判断大小/*if (prices[j]-prices[i]>max) {max = prices[j]-prices[i];}*///方法二：用表达式。max = prices[j] - prices[i] > max ? prices[j] - prices[i] : max;}list.add(max);}System.out.println("list" + list);res = Collections.max(list);return res;}//方法二：可以通过public int maxProfit2(int[] prices) {int min = Integer.MAX_VALUE;int res = 0;for (int i = 0; i < prices.length; i++) {if (prices[i] < min)min = prices[i];//min数组中最小值else if (prices[i] - min > res)res = prices[i] - min;}return res;}

LeetCode 100. 相同的树
LeetCode 101. 对称二叉树
LeetCode 102. 二叉树的层序遍历
LeetCode 103. 二叉树的锯齿形层序遍历
LeetCode 104. 二叉树的最大深度
LeetCode 105. 从前序与中序遍历序列构造二叉树
LeetCode 107. 二叉树的层序遍历 II
LeetCode 108. 将有序数组转换为二叉搜索树
LeetCode 121. 买卖股票的最佳时机
LeetCode 122. 买卖股票的最佳时机 II
LeetCode 136. 只出现一次的数字

声明：
        题目版权为原作者所有。文章中代码及相关语句为自己根据相应理解编写，文章中出现的相关图片为自己实践中的截图和相关技术对应的图片，若有相关异议，请联系删除。感谢。转载请注明出处，感谢。

By luoyepiaoxue2014

B站： https://space.bilibili.com/1523287361 点击打开链接
微博： http://weibo.com/luoyepiaoxue2014 点击打开链接