算法（一）单调栈

2018-03-20

本文简单介绍一下单调栈的使用

1. 什么是单调栈

顾名思义，栈里面存储的数据是单调的，单调栈的主要应用是在构造单调栈的时候，利用其属性进行相关操作。

2. 单调栈的构造过程/性质

2.1单调递增栈

insert x
while stack and stack[-1] > x
    stack.pop()
stack.push(x)

2.2单调递减栈

insert x
while stack and stack[-1] < x
    stack.pop()
stack.push(x)

2.3 举例分析

给定数组[9,4,5,2,3,8]

构造单调递增栈，栈的数据变化过程为[9]->[4]->[4,5]->[2]->[2,3]->[2,3,8]

构造单调递减栈，栈的数据变化为[9]->[9,4]->[9,5]->[9,5,2]->[9,5,3]->[9,8]

2.4单调栈性质

单调栈内元素的单调的
每个数据都会执行进栈操作
使用单调栈可以找到某个元素左边/右边第一个大于或者小于当前元素的值。

3.单调栈的应用场景

用于寻找一个数组中，某个元素左边/右边第一个大于或者小于当前元素的值。
如果某个元素大于前面元素以后，前面元素变得失去了意义，那就构造单调递减栈
如果某个元素小于前面的元素，前面的元素变得失去了意义，就构造单调递增栈

3.1 如果想寻找左边或者右边第一个小于某元素的值，就构造单调递增栈

寻找第一个左边小于某元素的值寻找x左边第一个小于x的值，x进栈时，栈顶元素就是左边第一个比自己小的数。每个元素都会进栈一次，所以在x进栈之前，栈顶元素就是数组中，第一个小于当前元素x的数
寻找第一个右边小于某元素的值寻找x右边第一个小于x的值，在构建递增栈的过程中，每个元素都会进栈一次，只需要查看栈顶元素什么时候pop，在pop的时候就意味着找到了第一个比栈顶元素大的数（如果比栈顶小，就直接进栈了）。所以只需要记录栈顶pop的时候，该栈顶元素之后第一个大于自己的元素就找到了。对于遍历完之后，还在栈中的数据，说明该数组中，没有右边小于自己的数。

3.2 如果想寻找左边或者右边第一个大于某元素的值，就构造单调递减栈。

4. 单调栈leetcode参考

4.1 链表中的下一个更大节点

题目实际上就是，寻找链表中某元素后面第一个比他大数，显然就是构造递减栈。

递减栈，构造递减栈，以栈顶元素为基准，如果新插入的元素大于栈顶元素，那么该元素就是栈顶元素之后，第一个比栈顶元素大的数。然后该元素尝试入栈。删除栈顶元素。新的栈顶元素递归上述操作。可以看出，栈顶元素在出站的那一刻找到了后面第一个比自己大的数据。当然只有出站的数据找到了下一个更大节点，保留在栈里面的没有找到。

另外一种递减栈的实现，先将链表转成数组，从数组逆向看，就是前面第一个大于自己的数，就可以通过构造递减栈，刷新完递减栈以后，栈顶元素就是左边第一个大于自己的数。如果栈为空，那么说明前面没有比自己大的元素。

https://leetcode-cn.com/problems/next-greater-node-in-linked-list/

4.2 移掉K位数字

给定一个数字字符串，移除k位数字，使得剩余数字字符组成的数字最小。

显然数字的高位越小越好。

举例分析：

数字字符串“145237473”，k为3

整个选数的过程如下1->14->145->142->12->123->1237->1234->123473

显然这就是一个递增队列的构造过程，只是做了限制，我们只能pop k次。

https://leetcode-cn.com/problems/remove-k-digits/