[leetcode/lintcode 题解] 算法面试真题详解:最终优惠价-阿里云开发者社区

开发者社区> 算法编程> 正文
登录阅读全文

[leetcode/lintcode 题解] 算法面试真题详解:最终优惠价

简介: [leetcode/lintcode 题解] 算法面试真题详解:最终优惠价

描述
一位店主需要完成一项销售任务,他将要出售的物品排成一排。
从左侧开始,店主以其全价减去位于该物品右侧的第一个价格较低或价格相同的商品的价格。
如果右侧没有价格低于或等于当前商品价格的商品,则以全价出售当前商品。
你需要返回每一个物品实际售出价格。

  • 数组 Prices 的长度范围是: [1, 100000]
  • Prices[i] 的整数范围是: [1, 1000000]

在线评测地址:领扣题库官网

样例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]
解释: 
每一个物品都保持原价,他们的右边都没有等于或者更低价格的物品

单调非递减栈来存储之前的值,当出现比栈顶所存值更小的值则可以更新之前的价格。
代码

class Solution:
    """
    @param prices: a list of integer
    @return: return the actual prices
    """
    def FinalDiscountedPrice(self, prices):
        # write your code here
        s, res = [], [prices[i] for i in range(len(prices))]

        for i in range(len(prices)):
                while len(s) != 0 and prices[s[-1]] >= prices[i]:
                        index = s[-1]
                        s.pop()
                        res[index] = prices[index] - prices[i]
                s.append(i);
        return res

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接