分类 数据结构与算法 下的文章

  栈这个数据结构有很多有趣的用途,这里总结一个很有用的使用方式,单调栈。单调队列同理,仅是后入先出变成先入先出。

单调栈


  单调栈是在满足数据后入先出的前提下,栈内数据满足单调递增或单调递减排列。

  如单调递增栈:数据 i 入栈,先判断当前栈顶数据是否小于 i ,若不满足则弹出栈顶数据,直到栈顶数据小于 i 或栈为空,再将 i 入栈。这样保证了任意数据 i 入栈时,栈中所有元素小于 i,且满足先后顺序。

  我们考虑一个算法场景:给定一个非有序排列的数组 num[n],求数组中下标为 i 的数 num[i],其向左遍历第一个小于 num[i]的数。 如果我们无脑遍历,则需要在遍历数组本身的同时,从每一个 i 前向遍历出第一个小于 num[i] 的数。 算法复杂度在最坏情况下为 $$n^2$$。而若我们 使用单调栈,则能在只遍历一次数组 num 的同时,找出所有要求的数 ,算法复杂度降低到 $$n$$。因为当每一个数据 i 可以入栈时,当前单调栈栈顶的数就是满足要求的数。

阅读全文