首页 > 其他分享 >1475. 商品折扣后的最终价格

1475. 商品折扣后的最终价格

时间:2023-10-07 14:12:55浏览次数:46  
标签:mem 折扣 最终 top single 1475 prices stack 单调

链接

https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/description/

思路:

单调栈

  单调栈,顾名思义,就是在栈内,元素要么是单调递减的,要么是单调递增的。

  这个题目要求我们找下一个更小的元素,所以这个栈应当是递增的。(即栈顶元素最大)而我们要找的是下一个更小的元素,所以要从后往前遍历prices。

  单调栈的在线处理:我们在不断的生成单调栈的同时生成res。

代码

class Solution:
    def finalPrices(self, prices):
        mem = []
        single_stack = []
        for i in prices[::-1]:
            while len(single_stack) > 0:
                top = single_stack[-1]
                # 注意边界条件
                if top > i:
                    single_stack.pop()
                else:
                    break
            if len(single_stack) == 0:
                top = 0
            else:
                top = single_stack[-1]
            mem.append(i-top)
            single_stack.append(i)
        return mem[::-1]

 

标签:mem,折扣,最终,top,single,1475,prices,stack,单调
From: https://www.cnblogs.com/bjfu-vth/p/17746144.html

相关文章

  • 记录一次修不好的proxifier最终解决
    记录一次修不好的proxifier最终解决前言在做一道内网渗透题时,配置好frp和proxifier发现proxifier报了错误有cannotconfigurewindowsnetworktrytorunsyssettingtoolmanuallyError:Windowsnetwork(Winsock)isnotproperlyconfiguredtoworkwithProxifier......
  • 【分享】office 2007、2010、2013最终版分享 (转)
    转自宋永志博客,宋永志博客-最纯净的系统下载站(songyongzhi.com)Office2007SP3简体中文专业增强版2019.02(终结版)软件介绍:1、Office2007SP3专业增强版,集成补丁至2019年02月,集成正版序列号,安装完后自动激活。2、Office2007只有32位版本,可以兼容64位系统,请放心使用。3、......
  • printf 和scanf的用法(最终版)
    一 格式化输入函数scanfscanf函数的功能是格式化输入任意数据列表,其一般调用格式为:scanf(格式控制符,地址列表)【说明】(1)地址列表中给出各变量的地址,可以为变量的地址,以&开头,也可以为数组,字符串的首地址。(2)格式控制符由%和格式符组成,作用......
  • 数学最终讲义8-17章
    第8章第179页:第8章第180页:第8章第193页:第8章第194页:第8章第211页:第8章第215页:第11章第244页:第11章第247页:第11章第249页:第11章第250页:第11章第257页:第11章第269页:第12章第289页:第13章第304页:第13章第306页:第13章第317页:第14章第325页:第15章第350......
  • 假设 a 是一个由线程 1 和线程 2 共享的初始值为 0 的全局变量,则线程 1 和线程 2 同时
    假设a是一个由线程1和线程2共享的初始值为0的全局变量,则线程1和线程2同时执行下面的代码,最终a的结果不可能是()booleanisOdd=false;for(inti=1;i<=2;++i){if(i%2==1)isOdd=true;elseisOdd=false;a+=i*(isOdd?1:-1);}A:-1B:-2C:0D:1......
  • 可分离卷积(Separable Convolution)等价转换为传统卷积(Ordinary convolution)的方法,
    写在前面:可分离卷积提出的原因  卷积神经网络在图像处理中的地位已然毋庸置疑。卷积运算具备强大的特征提取能力、相比全连接又消耗更少的参数,应用在图像这样的二维结构数据中有着先天优势。然而受限于目前移动端设备硬件条件,显著降低神经网络的运算量依旧是网络结构优化的目......
  • 嵌入式三级知识点总结最终章
    181. 操作系统为软件系统提供了多任务运行环境等等而不是板级支持包,BSP运行之前,调试工具不能够用,BSP调试分两步 最小系统和外围设备驱动程序调试。182. RAM访问速度要比ROM快很多。183. U-Boot能够支持多种体系结构的处理器但是每种结构有其自身的版本。184. VXworks(微内核)......
  • 数学最终讲义18
    第18章第429页:第18章第436页:第18章第437页:第18章第441页:第18章第442页:第18章第444页:第18章第447页: ......
  • 数学最终讲义16-17
    第16章第385页:第16章第387页:第16章第387页:第16章第390页:第16章第391页:第16章第392页:第16章第397页:第16章第397页:第16章第398页:第16章第399页:第16章第400页:第17章第402页:(这个不确定理解的对不对)第17章第403页:第17章第405页:第17章第407页:第17章第410......
  • IOS-开发获取tableview中cell的最终渲染宽度
    如图 我想要实现一个cell,里面有一个白色的消息区域宽度是整个cell的宽度减少20pt, 于是我写了_msgview.frame=CGRectMake(10,_time.bounds.origin.x+30,self.contentView.bounds.size.width-20,80);贴上完整代码-(instancetype)initWithStyle:(UITableViewCellStyle)......