Monotonic Stack & Queue

Monotonic Stack

@Grandyang: 单调栈的一大优势就是 线性的时间复杂度，所有的元素只会进栈一次，而且一旦出栈后就不会再进来了。

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

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

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

一亩三分地的讨论：什么时候会用到单调栈（递增递减栈）的思想

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

LeetCode Example

• 42 Trapping Rain Water

• 84 Largest Rectangle in Histogram

• 85 Maximal Rectangle

• Next Greater Element I

• Daily Temperatures

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 by Li Yin

LeetCode Monotone Stack Summary 单调栈小结 by Grandyang

刷题笔记6（浅谈单调栈） by 法号桑菜

单调栈的介绍以及一些基本性质

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