单调栈与最近更大元素
约 55 分钟
单调栈与最近更大元素
先别猜算法，先把问题说清楚
今天只解决一个具体任务：求每个柱子作为最低柱时可形成的最大矩形。。上一节《表达式求值与优先级》已经产出一个可检查的状态或边界；今天不要清零重来，要把它带进《单调栈与最近更大元素》。 你先复述输入是什么、输出必须唯一满足什么、哪些输入合法、出现并列或无解怎样返回、能否修改输入、下标从零还是从一开始。若这些话写不完整，样例跑对也不能证明程序做的是同一道题。本节案例编号是 cs-08-leetcode/u07/l03/单调栈与最近更大元素/contract，后续代码、证明和测试都引用同一份契约。
为什么在这里学习它
本章要解决的是：根据候选元素的淘汰方向选择栈、队列、双端队列或堆，并用组合结构实现缓存。。本节不是孤立模板，它承担的连接是：单端淘汰解决最近关系，下一课处理先进先出的数据流。 我们会先保留一个显然正确但可能很慢的方案，再圈出重复工作；只有能指出被删掉的工作为何不影响答案，优化才有依据。面试时真正有价值的不是迅速喊出算法名，而是让对方看到你怎样从限制推出模型。
核心不变量和复杂度必须单独写
把这句话拆成三层。第一层是状态语义：变量、区间、栈、队列或 dp 项究竟代表哪一段已经完成的工作。第二层是保持性：本轮读入一个新元素后，怎样更新仍使语义成立。第三层是终止性：循环或递归结束时，这个语义为什么恰好推出题目要求的答案。复杂度要从元素进入、退出、比较或转移的次数累加，不能凭印象写 O(n)。
跟我从暴力基线走到优化
先为“求每个柱子作为最低柱时可形成的最大矩形。”写一个覆盖全部候选的基线，并用两三个最小输入说明它没有漏解。接着在纸上标出哪些区间、比较或子问题被反复计算。现在引入本节状态：每处理一步，都用一句话重述“已经完成什么、仍未知什么”。若要移动指针、弹栈、丢弃搜索区间或覆盖 dp，必须证明被丢掉的候选不可能成为更优答案。最后才写代码，并把每个分支对应回契约中的一种情况。
课堂上至少手推三组：普通输入用于看主流程；最小或空输入用于看初始化；带重复、并列、负数、极值或不可达状态的输入用于看边界。每轮写出关键状态，而不是只写最后答案。这样当程序错时，你能判断错误来自规格、模型、不变量、实现还是测试，而不是盲目换模板。（推导锚：cs-08-leetcode/u07/l03/单调栈与最近更大元素/trace。）
一个完整例题怎样讲给人听
围绕“求每个柱子作为最低柱时可形成的最大矩形。”，先给一个小输入，逐步列出状态表或指针位置；再解释为什么下一步只有当前动作安全。随后把规模扩大到约束上界，按“状态数 × 每状态工作量”核算时间，并把数组、哈希、递归栈或队列占用逐项计入空间。若存在两种方案，要比较它们依赖的前提，而不是一律选择渐近阶更低者：排序会改变顺序，哈希有额外空间，递归有栈深，位运算受数值范围限制。
今天最重要的失败边界
请故意构造这个失败：相等高度采用严格或非严格弹栈会影响边界；末尾需哨兵清栈。。先预测错误程序第一次在哪一轮偏离，再运行最小反例验证。只说“注意边界”不给分；必须写出输入、错误状态、错误输出和违反的契约。若修复需要新增特判，反问能否改写初始化或区间语义，让空输入、首尾元素和普通输入走同一条逻辑。（反例锚：cs-08-leetcode/u07/l03/单调栈与最近更大元素/counterexample。）
在线编程题怎样严格验收
本课绑定的代码题使用真实 Python 3 标准输入输出，不是伪代码。先在编辑器中写可运行基线，再提交优化版。基础任务至少六组、标准任务至少八组、挑战任务至少十组测试，覆盖普通、最小、空或单元素、重复/并列、极值、不可达以及复杂度压力。判题通过只证明这些可观察输入输出满足契约；你还要在题解里说明不变量、复杂度和未覆盖风险。
随课四题怎么做
单选题检查哪一种推理链成立；多选题同时验收规格、不变量、复杂度和反例，漏选或多选均错；状态计算题要求把简化操作次数算出来并说明模型；证明题按十分量表评分：契约与基线2分，不变量与保持性3分，终止和正确性2分，复杂度1分，失败边界与测试2分。只贴最终代码、只写算法名或只报复杂度不能证明已经学会。
下课前闭卷交付
不看正文，用五分钟完成一页题解：一句话契约；一个暴力基线；状态语义；初始化—保持—终止证明；时间和空间来源；“相等高度采用严格或非严格弹栈会影响边界；末尾需哨兵清栈。”的最小反例；六到十组测试分类；最后口述如何完成“求每个柱子作为最低柱时可形成的最大矩形。”。下一节《循环队列与容量语义》会直接使用今天留下的状态、反例或复杂度结论。 如果其中任何一项只能靠背诵恢复，就回到对应代码行重新手推。（闭环锚：cs-08-leetcode/u07/l03/单调栈与最近更大元素/handoff。）
Practice
本课练习
先独立作答再提交；编程题会在隔离沙箱中真实编译、运行并对拍。
在《单调栈与最近更大元素》中，若每个元素恰好完成一次主处理，输入规模 n=64 时主处理次数是多少？ 先写采用的计数模型，并说明它为何只是一种上界估算。
本题专题为《单调栈与最近更大元素》。围绕“求每个柱子作为最低柱时可形成的最大矩形。”写完整题解：契约、暴力基线、状态语义、初始化—保持—终止证明、时间/空间来源、针对“相等高度采用严格或非严格弹栈会影响边界；末尾需哨兵清栈。”的最小反例和分层测试。只贴代码不得分。
输出数据流当前第k大值。 输入：第一行 n、k，第二行数据流。 输出：每读取一项输出当前第k大；不足k项输出NA。 约束：1≤k≤n≤200000。 使用 Python 3 从标准输入读取，向标准输出写出唯一规定结果；不得读取文件或网络。 使用 Python 3 标准输入输出；不得使用第三方包。必须覆盖题面边界，不能只针对样例。