背景

我们先举一个生活中的例子。几位同学排成一行，每个人都会被排在前面的第一个比他高的人挡住视线。如何得到每个人前面第一个比他高的人的位置呢？

我们将这个问题形式化描述一下，给定一个长度为n的数组a[]，表示n位同学的身高，请给出每位同学左侧第一个比他高的同学所在的位置。

暴力方法

伪代码

for (int i = 1; i <= n; i++) {
    for (int j = i; j >= 1; j--) {
        if (a[j] > a[i]) {
            i左侧第一个比i大的数就是j了
            break;
        }
    }
}

复杂度分析

算法包含两层for循环，时间复杂度为。

单调栈

我们知道，栈是一种单边开口，先进后出的数据结构。

介绍

单调栈分为单调递增栈（栈中元素从栈底到栈顶单调递增），单调递减栈（栈中元素从栈底到栈顶单调递减）。

我们拿[5, 1, 3, 2, 4]为例，模拟构建单调递减栈的过程。

扫描整个数组，当看到5时，由于栈中没有元素，我们将5加入栈中，此时栈中为[5。

看到1，由于1小于栈顶的5，我们可以直接将1加入到栈中，1左侧第一个比1大的数就是5了，此时栈中元素为[5, 1。

看到3，由于3比栈顶的1大，我们将1弹出，1右侧比1大的第一个数就是3了，栈中元素为[5，3比5小，将3入栈，[5, 3，此时可以确定3左侧第一个比3大的数是5。

看到2，由于2比栈顶元素3小，直接入栈，此时可以确定2左侧第一个比2大的数是3。栈中元素为[5, 3, 2。

看到4，由于4大于栈中2和3，我们会将2，3依次弹出，此时可以确定3和2右侧第一个比他们大的数就是4。此时栈中元素为[5，然后将4入栈，可以确定4左侧第一个比它大的数为5。

模拟结束，我们可以发现两个特点：

• 元素入栈时，可以确定它左侧第一个比它大的数。
  • 因为左侧比它小的数都会被它弹出去
  • 若入栈时，栈为空，则它左侧没有比它大的数。
• 元素出栈时，可以确定它右侧第一个比它大的数。
  • 因为它会被右侧第一个比它大的数弹出去
  • 若元素没有出栈，则它右侧没有比它大的数。

单调栈的意义

单调递减栈可以确定元素左右两侧第一个比它大的数。 单调递增栈可以确定元素左右两侧第一个比它小的数。

时间复杂度分析

由于每个元素最多只会入栈出栈一次，所以时间复杂度为。