03链表+栈+队列（D2

03链表+栈+队列（D2_栈）

讲解一：栈

一、基本介绍

二、代码示例

------------------------------

讲解二：单调栈

一、基本介绍

二、适用场景

三、情形示例

1. 寻找左边第一个小于它的数

2. 寻找左边第一个小于它的数的下标

3. 寻找右边第一个大于它的数

4. 寻找右边第一个大于它的数的下标

七、知识小结

讲解一：栈

一、基本介绍

栈(stack)是一个有序线性表，只能在表的一端(称为栈顶，top)执行插人和删除操作，后插入的元素

将是第一个被删除。所以，栈也称为后进先出(LastInFirstOut，LIFO)或先进后出(First In Last

Out，FILO)线性表。

一个称为入栈(push)，表示在栈中插入一个元素;
另一个称为出栈(pop)，表示从栈中删除一个元素。

试图对一个空栈执行出栈操作称为下溢(underflow);

试图对一个满栈执行人栈操作称为溢出(overflow)。

通常，溢出和下溢均认为是异常。

二、代码示例

示意图

实现

使用数组实现的叫静态栈
使用链表实现的叫动态栈

------------------------------

讲解二：单调栈

一、基本介绍

🍐单调栈分为单调递增栈和单调递减栈，通过使用单调栈我们可以访问到最近一个比它大（小）

的元素。

🍊 单调递增栈：单调递增栈就是从栈底到栈顶数据是依次递增，通常是寻找某方向第一个比它小

的元素。

🍊 单调递减栈：单调递减栈就是从栈底到栈顶数据是依次递减，通常是寻找某方向第一个比它大

的

二、适用场景

什么情况适合用单调栈来解决实际问题呢？

通常是在数组中需要通过比较前后元素的大小关系来找最近的比它大（小）的元素问题时，可以使

用单调栈进行求解。

三、情形示例

1. 寻找左边第一个小于它的数

题目描述： 给定一个长度为 n ≤ 10 ^5 的数组 a，输出每个数左边第一个比它小的数，如果不存在则输出 − 1。

【常规思路】

双重循环来做，第一重循环枚举每个数，第二重循环找出指定区间类第一个满足条件的数。

然而这种做法的复杂度是O（n^2）利用单调栈，我们可以将复杂度降低至O(n)。

在指针 i 从左往右遍历的过程中，我们可以用一个栈来保存 i 左边的所有元素（不包括i指向的元素），下标越大的元素越接近栈顶，
下标越小的元素越接近栈底。
每次我们访问栈顶，只要栈顶元素大于等于 a [ i ]，我们就将栈顶元素弹出，直至栈顶元素小于 a [ i ]，此时输出栈
顶元素并将 a [ i ] 压入栈中。由于栈中保存了 i 左边的所有元素，所以只要有答案，则答案一定在栈中。
由于每个元素一定会被压入一次且至多弹出一次，因此操作次数至多是2n，故总时间复杂度为O(n)。

Java代码如下：

public class Main {
    static int N = (int) (1e5 + 10);
    static int[] a = new int[N], ans = new int[N];
    static Deque<Integer> stack = new LinkedList<>();
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) throws IOException {
        in.nextToken();
        int n = (int) in.nval;
        for (int i = 0; i < n; i++) {//存数组
            in.nextToken();
            a[i] = (int) in.nval;
        }

        for (int i = 0; i < n; i++) {//单调栈模板（注意是数值）
            while (!stack.isEmpty() && stack.peekFirst() >= a[i]) stack.poll();
            if (!stack.isEmpty()) ans[i] = stack.peekFirst();
            else ans[i] = -1;
            stack.push(a[i]);
        }

        for (int i = 0; i < n; i++) {//输出结果
            System.out.print(ans[i] + " ");
        }
    }
}

下面，我们再来看看其他几种情况，基本上都是大同小异。

2. 寻找左边第一个小于它的数的下标

public class Main {
    static int N = (int) (1e5 + 10);
    static int[] a = new int[N], ans = new int[N];
    static Deque<Integer> stack = new LinkedList<>();
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) throws IOException {
        in.nextToken();
        int n = (int) in.nval;
        for (int i = 0; i < n; i++) {//存数组
            in.nextToken();
            a[i] = (int) in.nval;
        }

        for (int i = 0; i < n; i++) {//单调栈模板（注意是下标）
            while (!stack.isEmpty() && a[stack.peekFirst()] >= a[i]) stack.poll();//注意这里的第二个条件是a[stack.peekFirst()] 而不是stack.peekFirst()
            if (!stack.isEmpty()) ans[i] = stack.peekFirst();
            else ans[i] = -1;
            stack.push(i);//这里也不再是a[i]，而是存储对应的下标
        }

        for (int i = 0; i < n; i++) {//输出结果
            System.out.print(ans[i] + " ");
        }
    }
}

3. 寻找右边第一个大于它的数

题目描述： 给定一个长度为 n ≤ 10 ^5 的数组 a，输出每个数右边第一个比它大的数，如果不存在

则输出 − 1。之前我们是在一个数的左边去寻找，所以让栈去保存这个数左边的所有数，类似地，

现在需要让栈去保存这个数右边的所有数考虑将数组翻转（倒序遍历），因此情形三变成了「寻找

一个数左边第一个大于它的数」，属于情形一

Java代码如下：

public class Main {
    static int N = (int) (1e5 + 10);
    static int[] a = new int[N], ans = new int[N];
    static Deque<Integer> stack = new LinkedList<>();
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) throws IOException {
        in.nextToken();
        int n = (int) in.nval;
        for (int i = 0; i < n; i++) {//存数组
            in.nextToken();
            a[i] = (int) in.nval;
        }

        for (int i = n - 1; i >= 0; i--) {//单调栈模板（注意是数值）
            while (!stack.isEmpty() && stack.peekFirst() <= a[i]) stack.poll();
            if (!stack.isEmpty()) ans[i] = stack.peekFirst();
            else ans[i] = -1;
            stack.push(a[i]);
        }

        for (int i = 0; i < n; i++) {//输出结果
            System.out.print(ans[i] + " ");
        }
    }
}

4. 寻找右边第一个大于它的数的下标

题目描述： 给定一个长度为 n ≤ 10 ^5 的数组 a，输出每个数右边第一个比它大的数的下标，如果

不存在则输出− 1。结合情形二和情形三即可写出代码。

Java代码如下：

public class Main {
    static int N = (int) (1e5 + 10);
    static int[] a = new int[N], ans = new int[N];
    static Deque<Integer> stack = new LinkedList<>();
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) throws IOException {
        in.nextToken();
        int n = (int) in.nval;
        for (int i = 0; i < n; i++) {//存数组
            in.nextToken();
            a[i] = (int) in.nval;
        }

        for (int i = n-1; i >= 0; i--) {//单调栈模板（注意是下标）
            while (!stack.isEmpty() && a[stack.peekFirst()] <= a[i]) stack.poll();
            if (!stack.isEmpty()) ans[i] = stack.peekFirst();
            else ans[i] = -1;
            stack.push(i);
        }

        for (int i = 0; i < n; i++) {//输出结果
            System.out.print(ans[i] + " ");
        }
    }
}

总结以上情形：