JZTXT

算法--笔记--单调栈

发布时间 2023-11-06 19:57:58作者: 山雨欲來風滿楼

单调栈是为了解决两层foru循环O(n^2) 变为O(n)的问题

思路是：

  1. 维持一个单调栈.

  2. 依次进入单调栈，并淘汰对后续没有帮助的对象

  3. 当一个对象从栈里弹出的时候，结算当前对象参与的答案。

如何判断单调栈是大压小还是小压大呢？

  • 左侧的要小的，就是大压小

  • 左侧的要大的，就是小压大