V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hakunamatata11
V2EX  ›  推广

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

  •  
  •   hakunamatata11 · 2020-06-09 14:45:28 +08:00 · 975 次点击
    这是一个创建于 1627 天前的主题,其中的信息可能已经有所发展或是发生改变。

    [题目描述]

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

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

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

    在线评测地址: 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
        1
    orangey  
       2020-06-10 08:28:37 +08:00 via Android
    不懂算法,想问一下 这个用二分也可以做吧?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2644 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 19ms · UTC 04:21 · PVG 12:21 · LAX 20:21 · JFK 23:21
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.