Leetcode_121

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0

方法：单调栈

维护一个单调递增的栈，如果新的数大于栈顶数据，那么直接入栈，如果小于，弹出栈顶，将栈顶和栈底元素做差，维护最大值。同时最终需要所有元素出栈，所以设置最后一个元素为1-。

public class Leetcode_121 {public static void main(String[] args) {int[] prices = {7, 1, 5, 3, 6, 4};int result = maxProfit(prices);System.out.println(result);}public static int maxProfit(int[] prices) {int n = prices.length;int[] temp = new int[n+1];for(int i=0;i<n;i++){temp[i] = prices[i];}temp[n] = -1;//保证所有元素出栈int ans = 0;//ArrayDeque 可以当作栈、双端队列使用ArrayDeque<Integer> stack = new ArrayDeque<>();for(int i=0;i< temp.length;i++){while(!stack.isEmpty()&& stack.peek()>=temp[i]){int top = stack.pop();if(stack.isEmpty()){continue;}ans = Math.max(ans,top-stack.peekLast());}stack.push(temp[i]);}return ans;}}