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

[hakunamatata11]

[题目描述]

一位店主需要完成一项销售任务，他将要出售的物品排成一排。 从左侧开始，店主以其全价减去位于该物品右侧的第一个价格较低或价格相同的商品的价格。

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

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

在线评测地址: https://www.lintcode.com/problem/final-discounted-price/?utm_source=sc-v2ex-fks

示例 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-v2ex-fks

[orangey]

不懂算法，想问一下 这个用二分也可以做吧？