单调栈

单调栈

单调栈实际上就是栈,只是限制要比普通的栈更严格而已了。要求是每次入栈的元素必须要有序(如果新元素入栈不符合要求,则将之前的元素出栈,直到符合要求再入栈),使之形成单调递增/单调递减的一个栈。

  • 单调递增栈:只有比栈顶小的才能入栈,否则就把栈顶出栈后,再入栈。出栈时可能会有一些计算。适用于求解第一个大于该位置元素的数。
  • 单调递减栈:与单调递增栈相反。适用于求解第一个小于该位置元素的数。

如何判断

单调递增/递减栈是根据出栈后的顺序来决定的。例如,栈内顺序[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);
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注