2019-数据结构-数据结构3.2-单调栈

数据结构3.2-单调栈

1. 什么是单调栈?

1. 从名字上就听的出来，单调栈中存放的数据应该是有序的，所以单调栈也分为单调递增栈和单调递减栈
   1. 单调递增栈：数据出栈的序列为单调递增序列
   2. 单调递减栈：数据出栈的序列为单调递减序列
2. 这里一定要注意所说的递增递减指的是出栈的顺序，而不是在栈中数据的顺序

2. 单调栈的性质

1. 利用单调栈，我们可以找到从左/右遍历第一个比它小/大的元素的位置
2. 一个元素向左遍历的第一个比它小的数的位置就是将它插入单调栈时栈顶元素的值，若栈为空，则说明不存在这么一个数。然后将此元素的下标存入栈，就能类似迭代般地求解后面的元素

3. 单调递增栈的实现

1. 如果入栈元素大于栈顶元素，则直接入栈
2. 如果入栈元素小于栈顶元素，则需要出栈知道大于栈顶元素，然后依次按照顺序入栈。

4. 单调栈例题

1. 单调栈总结