> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/problem-solving-summary/monotonic-stack.md).

# Monotonic Stack & Queue

## Monotonic Stack

[**@Grandyang**](http://www.cnblogs.com/grandyang/p/8887985.html): 单调栈的一大优势就是 **线性的时间复杂度**，所有的元素只会进栈一次，而且一旦出栈后就不会再进来了。

**单调递增栈可以找到左起第一个比当前数字小的元素**。

**单调递减栈可以找到左起第一个比当前数字大的元素。**

Tips: 栈中可以存下标，也可以直接存元素。

一亩三分地的讨论：[什么时候会用到单调栈（递增递减栈）的思想](https://www.1point3acres.com/bbs/thread-204388-1-1.html)

> 单调栈何时用： 为任意一个元素找左边和右边第一个比自己大/小的位置，用单调栈 用递增单调栈还是递减单调栈：递减栈会剔除波谷，留下波峰；递增栈剔除波峰，留下波谷

**LeetCode Example**

* 42 [Trapping Rain Water](/lintcode/two_pointers/trapping_rain_water.md)
* 84 [Largest Rectangle in Histogram](/lintcode/stack/largest_rectangle_in_histogram.md)
* 85 [Maximal Rectangle](/lintcode/stack/maximal-rectangle.md)
* [Next Greater Element I](/lintcode/stack/next-greater-element-i.md)
* [Daily Temperatures](/lintcode/stack/daily-temperatures.md)

## Monotonic Queue

> A monotonic Queue is a data structure the elements from the front to the end is strictly either increasing or decreasing.

**LeetCode Example**

* 581 Shortest Unsorted Continuous Subarray
* 496 Next Greater Element I
* 503 Next Greater Element II
* 862 Shortest Subarray with Sum at Least K
* 84 Largest Rectangle in Histogram
* 122 Best Time to Buy and Sell Stock II

## Resource, Reference and Reading List

[Monotonic Queue Explained with LeetCode Problems](https://medium.com/algorithms-and-leetcode/monotonic-queue-explained-with-leetcode-problems-7db7c530c1d6) by Li Yin

[LeetCode Monotone Stack Summary 单调栈小结](https://www.cnblogs.com/grandyang/p/8887985.html) by Grandyang

[刷题笔记6（浅谈单调栈）](https://zhuanlan.zhihu.com/p/26465701) by 法号桑菜

[单调栈的介绍以及一些基本性质](https://blog.csdn.net/liujian20150808/article/details/50752861)

<https://github.com/liyin2015/Algorithms-and-LeetCode>