121.买卖股票的最佳时机

class Solution {public int maxProfit(int[] prices) {int min = prices[0];int max = 0;for (int i = 1; i < prices.length; i++) {max = Math.max(prices[i] - min, max);if (prices[i] < min) {min = prices[i];}}return max;}
}

小结：贪心可以将O(n²)的时间复杂度降为O(n)，只需要额外使用空间维护已经遍历过的数里面的最小值即可。