【LeetCode】121. 买卖股票的最佳时机
LeetCode 股票 买卖 最佳时机 121
2023-09-27 14:29:07 时间
给定一个数组 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
思路:
简单的贪心算法解决即可。
贪心算法:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。
代码:
#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std ;
int prices[10000] ;
int main()
{
int n ;
cin >> n ;
for(int i=0; i<n; i++)
{
cin >>prices[i] ;
}
int sum = 0 ;
int mi = 0x3f3f3f ;
int len = n ;
for(int i=0; i < len; i++)
{
mi = min(mi, prices[i]) ;
sum = max(sum, prices[i]-mi) ;
}
cout << sum << endl ;
return 0 ;
}
相关文章
- 【LeetCode】买卖股票的最佳时机含手续费 [M](动态规划)
- LeetCode_动态规划_困难_1326.灌溉花园的最少水龙头数目
- LeetCode_二叉树_简单_226.翻转二叉树
- LeetCode_动态规划_困难_887.鸡蛋掉落
- LeetCode_动态规划_困难_188.买卖股票的最佳时机 IV
- LeetCode_动态规划_中等_122.买卖股票的最佳时机 II
- LeetCode_动态规划_简单_121.买卖股票的最佳时机
- LeetCode_字符串_简单_28.实现strStr()
- 【LeetCode】第1天 - 121.买卖股票的最佳时机
- [LeetCode-21]Construct Binary Tree from Preorder and Inorder Traversal
- [LeetCode] 245. Shortest Word Distance III 最短单词距离 III
- [LeetCode] 568. Maximum Vacation Days 最大化休假日
- [LeetCode] 460. LFU Cache 最近最不常用页面置换缓存器
- [LeetCode] 123. Best Time to Buy and Sell Stock III 买卖股票的最佳时间 III
- [LeetCode] 286. Walls and Gates 墙和门
- leetcode算法: Average of Levels in Binary Tree
- leetcode 188 买卖股票的最佳时机IV
- leetcode 123买卖股票的最佳时机III
- LeetCode 121.买卖股票最佳时机 c语言