原题链接:http://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/这道题求进行一次交易能得到的最大利润。如果用brute force的解法就是对每组交易都看一下利润,取其中最大的,总用有n*(n-1)/2个可能交易,所以复杂度是O(n^2)。很容易感觉出来这是动态规划的题目,其实跟Maximum
Subarray非常类似,用“局部最优和全局最优解法”。思路是维护两个变量,一个是到目前为止最好的交易,另一个是在当前一天卖出的最佳交易(也就是局部最优)。递推式是local[i+1]=max(local[i]+prices[i+1]-price[i],0),
global[i+1]=max(local[i+1],global[i])。这样一次扫描就可以得到结果,时间复杂度是O(n)。而空间只需要两个变量,即O(1)。代码如下:public int maxProfit(int[] prices) {
if(prices==null || prices.length==0)
return 0;
int local = 0;
int global = 0;
for(int i=0;i<prices.length-1;i++)
{
local = Math.max(local+prices[i+1]-prices[i],0);
global = Math.max(local, global);
}
return global;
}
这种题目的解法非常经典,不过是比较简单的动态规划。这道题目还有两个变体,Best
Time to Buy and Sell Stock II和Best
Time to Buy and Sell Stock III,虽然题目要求比较像,但是思路却变化比较大,Best
Time to Buy and Sell Stock II可以交易无穷多次,思路还是比较不一样,而Best
Time to Buy and Sell Stock III则限定这道题交易两次,其实还可以general到限定交易k次,会在这道题目中仔细讲解,有兴趣的朋友可以看看哈。
分享到:
相关推荐
leetcode题目:Best Time to Buy and Sell Stock II
leetcode-java leetcode刷题笔记 已做题目列表 1.Two Sum 3.Longest Substring Without Repeating Characters 5.Longest Palindromic Substring 20.Valid Parentheses 26.Remove Duplicates from Sorted Array 53....
leetcode leetcode The optimum C++ solutions for the leetcode 这是我自己写的leetcode的题解,目前已经完成了70%左右,后续部分会很快更新 这里放上来的代码都能保证是最优解(复杂度最优) 当然有些题目因为测试...
leetcode LeetCode 解决题目的总数: 136/1753 微信公众号: 工程师Ruojhen 算法-动态规划 题号 名称 English Name 题解 53 最大子序和 Maximum Subarray 70 爬楼梯 Climbing Stairs 121 买卖股票的最佳时机 Best Time...
股票收益leetcode LeetCode 股票问题 Best Time to Buy and Sell Stock (Easy) 一次交易,找最大收益 for i in prices: low = min(low, i) profit = max(profit, i-low) Best Time to Buy and Sell Stock II (Easy) ...
股票买卖最佳时机leetcode GitFitCode 配对编码挑战! 买卖股票的最佳时机 让我们弄清楚什么时候买一些股票! 这不应该在现实生活中使用。 现在不管你认为你的算法有多好:)。 我确实鼓励您选择一只您感兴趣的股票,...
leetcode 分类 LeetCode LeetCode Java Solution 2018年5月31日 更新 最近刷了一遍 LeetCode,发现第一次的代码确实有些 low 很多代码并不简洁,本来1行的代码可以写成3行 思维混乱 没有按照题目类型分类 没有写结题...
LeetCode-Trip LeetCode刷题代码,大佬勿入。 为一年后的研究生找工作准备 目标是BAT的算法岗哈哈哈哈哈 争取做到每日一更 嗯…… 19.10.22:鸽了这么久,我又回来了……主要在实验室天天没啥事,过于佛系,刷刷题吧...
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...
圆和椭圆重叠leetcode ——#158 尖端 关心特殊情况 从不同的方向思考 简单的 大批 1.Two Sum -> 使用哈希表避免遍历列表448.查找数组中消失的所有数字-> 1.建立缓冲区来计算数字| 2.使用数组作为带符号的缓冲区118....
Best Time to Buy and Sell Stock [121]3. Climbing Stairs [70]4. Maximum Subarray [53]5. House Robber [198]6. Range Sum Query - Immutable [303]7. Counting Bits [338]8. Palindromic Substrings [647]9. ...
leetcode卡 leetcode exercises 3-5 solutions everyday. fighting~ TODO array Best Time to Buy and Sell Stock II Valid Sudoku linked list Palindrome linked list Linked List Cycle trees Convert Sorted ...
201 | [Bitwise AND of Numbers Range](https://leetcode.com/problems/bitwise-and-of-numbers-range/) | [C++](./C++/bitwise-and-of-numbers-range.cpp) [Python](./Python/bitwise-and-of-numbers-range.py) | _...
leetcode小岛出水口 leetcode training one problem on file 为了方便文档管理,项目逐渐文档化,以单个文件作为集合最小集。 go语言不能完全适合写算法题 后续会尽可能加入rust或者c的题解 清单 0965. Univalued ...
leetcode 浇花力扣解决方案 简单的 #0001 - Two Sum #0007 - Reverse Integer #0009 - Palindrome Number #0035 - Search Insert Position #0058 - Length of Last Word #0066 - Plus One #0083 - Remove Duplicates...
leetcode 第三题 java 介绍 欢迎!..."https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/", "beats": 0.9000, "category": ["dynamic-programming"], "tags": ["your-wh
leetcode 和 oj 力码下载器 您已接受的提交的下载器 依赖 只需运行pip install -r requirements.txt来安装它们 ...下载器将根据问题名称将您ACCEPTED提交内容提取到相应的目录中 ...best-time-to-buy-and-sell-stock
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ * * 思路: * 股票只能买卖一次 T+1 操作 * 最大利润 = 最高点 - 最低点 * 并且 最高点只能在 最低点的后面 * * */ public int maxProfit_1(int...
63. 股票的最大利润题目链接Leetcode:121. Best Time to Buy and Sell Stock题目描述可以有一次买入和一次卖出,买入必
leetcode中文版车鸟 一组用python编写的算法。 种类 ...best_time_to_buy_and_sell_stock_II binary_tree_inorder_traversal binary_tree_level_order_traversal binary_tree_level_order_traversal_I