package stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author dx
 * @version 1.0
 * @date 2022年3月31日 9:57
 * @description: 力扣 1475
 */
public class FinalPrices {

 public int[] finalPrices(int[] prices) {
 int len = prices.length;
 int [] ans = new int[len];
 Deque<Integer> stack = new LinkedList<Integer>();
 for(int i=len-1;i>=0;i--){

 while(stack.size()!=0 && stack.peek()>prices[i]){ //保证栈顶保留最近比当前price小的数
 stack.pop();
 }
 if(stack.size() == 0){
 ans[i] = prices[i]-0;
 }else{
 ans[i] = prices[i] - stack.peek();
 }
 stack.push(prices[i]); //当前price的入栈,参与"保证栈顶保留最近比当前price小的数"
 }
 return ans;
 }
}