[leetcode/lintcode 题解] 美团面试题：最终优

【题目描述】

一位店主需要完成一项销售任务，他将要出售的物品排成一排。

从左侧开始，店主以其全价减去位于该物品右侧的第一个价格较低或价格相同的商品的价格。

如果右侧没有价格低于或等于当前商品价格的商品，则以全价出售当前商品。

你需要返回每一个物品实际售出价格。

在线评测地址:

https://www.lintcode.com/problem/final-discounted-price/?utm_source=sc-js-mh0609

示例 1:

输入:
Prices = [2, 3, 1, 2, 4, 2]
输出: [1, 2, 1, 0, 2, 2]

解释：第0个和第1个物品右边第一个更低的价格都是1，所以实际售价需要在全价上减去1， 第3个物品右边第一个更低的价格是2，所以实际售价要在全价上面减去2。

示例 2:

输入:
Prices = [1, 2, 3, 4, 5]
输出: [1, 2, 3, 4, 5]

解释: 每一个物品都保持原价，他们的右边都没有等于或者更低价格的物品

【题解】

public class Solution {
    /**
     * @param prices: a list of integer
     * @return: return the actual prices
     */
    public int[] FinalDiscountedPrice(int[] prices) {
        // write your code here
        int[] res = new int[prices.length];
        Stack<Integer> s = new Stack<>();

        for(int i = 0;i < prices.length;i++) res[i] = prices[i];

        for(int i = 0;i < prices.length;i++){
            while(!s.isEmpty() && prices[s.peek()] >= prices[i]) {
                int index = s.pop();
                res[index] = prices[index] - prices[i];
            }
            s.push(i);
        }
        return res;
    }

更多语言代码参见：https://www.lintcode.com/problem/final-discounted-price/?utm_source=sc-js-mh0609