单调栈
单调栈实际上就是栈,只是限制要比普通的栈更严格而已了。要求是每次入栈的元素必须要有序(如果新元素入栈不符合要求,则将之前的元素出栈,直到符合要求再入栈),使之形成单调递增/单调递减的一个栈。
- 单调递增栈:只有比栈顶小的才能入栈,否则就把栈顶出栈后,再入栈。出栈时可能会有一些计算。适用于求解第一个大于该位置元素的数。
- 单调递减栈:与单调递增栈相反。适用于求解第一个小于该位置元素的数。
如何判断
单调递增/递减栈是根据出栈后的顺序来决定的。例如,栈内顺序[1, 2, 6],出栈后顺序[6, 2, 1],这就是单调递减栈。
适用场景
单调栈一般用于解决 第一个大于 xxx 或者 第一个小于 xxx 这种题目。
int[] ans = new int[T.Length];
Stack<int> stack = new Stack<int>();
for(int i = 0; i < T.Length; i++) {
while(stack.Count > 0 && T[i] > T[stack.Peek()]) {
int curI = stack.Pop();
ans[curI] = i - curI;
}
stack.Push(i);
}