0121. Best Time To Buy And Sell Stock
难度: Easy
刷题内容
原题连接
内容描述
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例1
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例2
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解题方案
思路1：DP **- 时间复杂度: O(N)*- 空间复杂度: O(2N)***
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
var lowestPrice = prices.shift()
var maxProfitCount = 0
while (prices.length) {
var current = prices.shift()
lowestPrice = Math.min(lowestPrice, current)
maxProfitCount = Math.max(current - lowestPrice, maxProfitCount)
}
return maxProfitCount
};
思路 2： 暴力穷举法 **- 时间复杂度: O(N²)*- 空间复杂度: O(2N)***
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
var profitList = []
while (prices.length) {
var cur = prices.shift()
profitList.push(Math.max(...prices) - cur)
}
var maxProfit = Math.max(...profitList)
return maxProfit > 0 ? maxProfit : 0
};
