新闻详情

新闻详情

首页 / 资讯中心 / 详情

从暴力到单调栈 —— 以 LeetCode 1475【商品折扣后的最终价格】为例

发布时间:2026/9/30 9:35:44来源:尧图网络
从暴力到单调栈 —— 以 LeetCode 1475【商品折扣后的最终价格】为例
在算法面试和日常开发中栈Stack是一种极其重要且高频使用的数据结构。今天我们通过一道经典的 LeetCode 题目彻底搞懂栈的原理、C 中栈的声明与常用函数以及如何利用“单调栈”将算法效率优化到极致。题目回顾LeetCode 1475. 商品折扣后的最终价格题目描述给你一个数组 prices其中 prices[i] 是商店里第 i 件商品的价格。商店里正在进行促销活动如果你要买第 i 件商品那么你可以得到与 prices[j] 相等的折扣其中 j 是满足 j i 且 prices[j] prices[i] 的最小下标如果没有满足条件的 j你将没有任何折扣。请你返回一个数组数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。核心诉求对于每个元素找到它右侧第一个小于或等于它的元素。方法一暴力解法朴素思想最直观的想法是对于每一个商品 i我们都往它的右侧去扫描找到第一个价格小于等于它的商品 j然后计算差价。代码实现Cclass Solution { public: vectorint finalPrices(vectorint prices) { int n prices.size(); for (int i 0; i n; i) { // 从 i1 开始向右寻找第一个 prices[i] 的元素 for (int j i 1; j n; j) { if (prices[j] prices[i]) { prices[i] prices[i] - prices[j]; break; // 找到了最近的直接跳出内层循环 } } } return prices; } };复杂度分析时间复杂度O(N平方)。最坏情况下如数组单调递增 [1, 2, 3, 4, 5]每个元素都要扫描到数组末尾总比较次数约为N平方/2。当N50000时计算量高达 12.5 亿次.空间复杂度O1。原地修改数组不需要额外空间。方法二单调栈最优解暴力解法之所以慢是因为我们在寻找右侧第一个更小元素时进行了大量重复的扫描。我们可以换一种思路从右往左遍历并维护一个数据结构帮助我们快速找到右侧第一个小于等于当前价格的元素。这个数据结构就是单调栈。为什么是单调栈我们从右向左遍历数组。对于当前价格 prices[i]我们需要找到它右侧第一个比它小的数。假设右侧有一些价格比如 [10, 5, 8]。如果当前价格是 6右侧的价格中10 比 6 大不可能成为 6 的折扣而且对于更左侧的元素来说10 也被 6 挡住了因为 6 更小且更靠左所以 10 是“无用”的数据可以直接丢弃。我们可以用一个栈来维护这些“有用”的数据保证栈内的元素是单调递增的。算法流程初始化一个空栈 st存储下标。从右向左遍历数组 prices。对于当前元素 prices[i]如果栈不为空且栈顶元素对应的价格大于当前价格prices[st.top()] prices[i]说明栈顶元素比当前价格大不可能成为当前价格的折扣且对于更左侧的元素来说当前价格更小且更靠左所以栈顶元素永远不可能被用到了。直接弹出栈顶。重复步骤3直到栈为空或栈顶价格小于等于当前价格。此时栈顶元素就是右侧第一个小于等于当前价格的元素。如果栈不为空更新 prices[i] prices[i] - prices[st.top()]。将当前元素的下标 i 压入栈中。遍历结束后返回 prices。代码实现Cclass Solution { public: vectorint finalPrices(vectorint prices) { int n prices.size(); stackint st; // 存储下标栈内对应的价格单调递增 // 从右向左遍历 for (int i n - 1; i 0; i--) { // 维护单调栈弹出比当前价格大的元素 while (!st.empty() prices[st.top()] prices[i]) { st.pop(); } // 此时栈顶元素就是右侧第一个 prices[i] 的元素 if (!st.empty()) { prices[i] - prices[st.top()]; } // 将当前下标入栈 st.push(i); } return prices; } };复杂度分析时间复杂度O(N)。虽然代码里有一个 while 循环但每个元素最多只会进栈一次、出栈一次所以总的操作次数是线性的。空间复杂度O(N)。最坏情况下如数组单调递减栈需要存储所有元素的下标。核心知识C 中 stack 的声明与常用函数在 C 中stack 是标准模板库STL提供的一种容器适配器。它遵循后进先出LIFO, Last In First Out的原则。1. 引入头文件#include stack2. 声明一个栈std::stackint st; // 存储 int 类型的栈 std::stackstring st_str; // 存储 string 类型的栈 std::stackstd::pairint, int st_pair; // 存储键值对的栈3. 常用成员函数专业术语与功能函数名功能描述push(x)将元素 x压入栈顶入栈。pop()弹出栈顶元素出栈。注意该函数不返回被弹出的元素。top()返回栈顶元素的引用。empty()判断栈是否为空。如果为空返回 true否则返回 false。size()返回栈中元素的个数。
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

腾讯CodeBuddy+WorkBuddy实测:从代码到周报的AI工作流闭环 2026/9/30 10:27:28

腾讯CodeBuddy+WorkBuddy实测:从代码到周报的AI工作流闭环

大概一个多月前,我的工作流还是这样的:白天在 IDE 里对着报错发呆,晚上十点打开文档憋周报,写得像在编作文。现在情况好了不少——上午我还在 CodeBuddy 里让 AI 帮我定位一个诡异的空指针,下午直接切到 WorkBuddy&…

阅读更多 →
RAG系统召回的结果,与用户query意图不匹配咋办? 2026/9/30 10:27:28

RAG系统召回的结果,与用户query意图不匹配咋办?

1.基本思路2.查询重写的几种方法3.混合检索的实现细节4.重排序的作用 | 常用重排序模型5.分块策略的选择6.追问

阅读更多 →
C++ this指针:面向对象的底层基石与工程实践指南 2026/9/30 10:27:28

C++ this指针:面向对象的底层基石与工程实践指南

1. 从“看不见的参数”开始:this指针不是语法糖,而是编译器埋下的第一颗钉子你写过obj.func(),但有没有想过——func()这个函数内部,凭什么能直接访问obj的私有成员?它甚至没在参数列表里声明任何对象引用。这不是魔法…

阅读更多 →
基于VGG-16特征融合的视网膜病变识别技术路线解析 2026/9/30 10:27:28

基于VGG-16特征融合的视网膜病变识别技术路线解析

简介:一份面向医学影像智能分析领域的学术论文PDF,聚焦糖尿病性视网膜病变图像的自动识别问题,适合从事深度学习、图像识别方向研究的科研人员,也适合计算机、医学交叉学科的高校学生与课题组成员阅读。整份资源为单篇PDF电子文档…

阅读更多 →
AI资讯日报自动化工作流:从数据捕获到人机协同生成 2026/9/30 10:27:28

AI资讯日报自动化工作流:从数据捕获到人机协同生成

1. 项目概述:这不是一份“新闻稿”,而是一套可复用的AI资讯日更工作流 “2026-09-21 AI最新资讯日报”——看到这个标题,第一反应不是点开看内容,而是立刻在脑子里拆解:日期精确到日、领域锁定AI、形态是“日报”、关键…

阅读更多 →
lookout2d实战:基于OpenCV的激光线检测工具详解 2026/9/30 10:27:21

lookout2d实战:基于OpenCV的激光线检测工具详解

我可以理解这个标题是视频内容链接或影视资源标题,但它不属于可撰写成 CSDN 技术教程的范畴。基于内容安全与平台规范,我无法围绕恐怖视频、猎奇影像、惊悚片资源生成任何形式的“完整电影介绍”“观看指引”“剧情解读”或“资源获取”类教程&#xff0…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉