Problem: 121. 买卖股票的最佳时机

思路

假设今天卖出，那怎么样收益最大呢？之前买入价是最低的

复杂度

⏰ 时间复杂度: ： $O(n)$
🌎 空间复杂度: $O(1)$

Code

class Solution {
	public int maxProfit(int[] prices)
	{
		int n = prices.length;
		if (n == 0)
			return 0;
		int min = prices[0];//维护当前元素前边最小值
		int ans = 0;
		for (int i = 1; i < n; i++)
		{
			if (prices[i] - min > ans)
				ans = prices[i] - min;//当前价格 - 之前最小 【最优策略】
			min = Math.min(min, prices[i]);
		}
		return ans;
	}
}