首页 > 代码库 > 【LeetCode】Best Time to Buy and Sell Stock
【LeetCode】Best Time to Buy and Sell Stock
题意:
Say 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.
思路:
只能买卖一次,所以要找一个最大差值的两天,但要注意低的那一天是在前面的。所以可以维护一个最小值和一个最大差值,从前往后走,如果比最小值小则更新,如果减最小值的差值大于之前的最大差值,则更新最大差值。
注意如果维护的是最大值和最小值,最后返回一个最大-最小的数,会是错的哦!
代码:
C++:
class Solution { public: int maxProfit(vector<int> &prices) { int n = prices.size(); if(n <= 1) return 0; int min_value = http://www.mamicode.com/prices[0];>Python:
class Solution: # @param prices, a list of integer # @return an integer def maxProfit(self, prices): if len(prices) < 2: return 0 min = prices[0] profit = 0 for x in prices: if x < min: min = x if x - min > profit: profit = x-min return profit【LeetCode】Best Time to Buy and Sell Stock
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。