新闻详情

新闻详情

首页 / 资讯中心 / 详情

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

发布时间:2026/11/18 16:52:41来源:尧图网络
从暴力到单调栈 —— 以 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

相关资讯

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

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/17 7:04:08

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/18 14:20:46

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/17 19:43:34

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/18 11:04:06

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/18 15:55:22

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/17 19:43:32

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

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

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