[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

相关文章
|
10天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
1月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
1月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
32 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
26天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
1月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
23 2
|
1月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
1月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
67 2
|
3月前
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
|
9天前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
|
10天前
|
存储 缓存 Java
大厂面试必看!Java基本数据类型和包装类的那些坑
本文介绍了Java中的基本数据类型和包装类,包括整数类型、浮点数类型、字符类型和布尔类型。详细讲解了每种类型的特性和应用场景,并探讨了包装类的引入原因、装箱与拆箱机制以及缓存机制。最后总结了面试中常见的相关考点,帮助读者更好地理解和应对面试中的问题。
34 4