题解 | #买卖股票的最好时机(一)#

public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int len = prices.length;
		Stack<Integer> s = new Stack<>();

		// 可以在 prices[len] 位置放一个 -1 的哨兵
		// 这样可以让单调递增的数组中所有的元素逼出去
		int ans = 0;
		for (int i = 0; i < prices.length; i++) {
			while (s.size() > 0 && s.peek() > prices[i]) {
				ans = Math.max(ans, s.peek() - s.firstElement());
				s.pop();
			}
			s.add(prices[i]);
		}

		// 模拟哨兵行为
		if (s.size() > 0)
			ans = Math.max(ans, s.peek() - s.firstElement());

		return ans;
    }
}