Best Time to Buy and Sell Stock
Question
- leetcode: Best Time to Buy and Sell Stock | LeetCode OJ
- lintcode: (149) Best Time to Buy and Sell Stock
1
2
3
4
5
6
7
8
9Say you have an array for
which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction
(ie, buy one and sell one share of the stock),
design an algorithm to find the maximum profit.
Example
Given an example [3,2,3,1,2], return 1
题解
最多只允许进行一次交易,显然我们只需要把波谷和波峰分别找出来就好了。但是这样的话问题又来了,有多个波峰和波谷时怎么办?——找出差值最大的一对波谷和波峰。故需要引入一个索引用于记录当前的波谷,结果即为当前索引值减去波谷的值。
Python
1 | class Solution: |
C++
1 | class Solution { |
Java
1 | public class Solution { |
源码分析
善用max
和min
函数,减少if
的使用。
复杂度分析
遍历一次 prices 数组,时间复杂度为 \[O(n)\], 使用了几个额外变量,空间复杂度为 \[O(1)\].
Reference
- soulmachine 的卖股票系列
Best Time to Buy and Sell Stock