单调栈-java

本次主要通过数组模拟单调栈来解决问题。

一、单调栈☀

二、算法思路☀

1.暴力做法🌙

2.优化做法🌙

3.单调递增栈和单调递减栈🌙

三、代码如下☀

1.代码如下（示例）：🌙

2.读入数据🌙

3.代码运行结果🌙

总结

前言☀

本次主要通过数组模拟单调栈来解决问题。

提示：以下是本篇文章正文内容，下面案例可供参考

一、单调栈☀

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

输入格式

第一行包含整数 N，表示数列长度。

第二行包含 N个整数，表示整数数列。

输出格式

共一行，包含 N个整数，其中第 i个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。

数据范围

1≤N≤100000
1≤数列中元素≤10^9

二、算法思路☀

我们引入一个整型数组arr来存储序列。

1.暴力做法🌙

图1.1思路模拟

我们要找寻数组中的每一个数的左边离它最小的数，如果找到就输出这个数；如果不存在的话就输出-1。那么我们就可以通过枚举数组中的每一个数，i表示数组中的第i个数。然后我们里面再写一层循环，用来枚举从数组第i-1个数到数组第1个数，用j来表示数组中第j个数。那么我们只需要来判断此时的数组第j个数是否小于第i个数即arr[j] < arr[i]，如果小于的话，打印数组中的第j个数退出内循环，外循环接着进行下一层，依次类推。代码如下:

        for(int i = 1;i <= n;i++ ){
            for(int j = i - 1;j >= 1;j--){
                if (arr[j] < arr[i]){
                    //找到了，退出内层循环
                    pw.println(arr[j]);
                    break;
                }
            }
            //不存在，输出-1
            pw.println(-1);
        }

可以看出我们的时间复杂度是O(n^2)，整数N的范围是到10^5，这样肯定会超时。

2.优化做法🌙

我们引入一个一维整型数组stack用来模拟栈；一个整型变量top表示栈顶指针。

图2.1 栈中元素模拟

因为我们需要找到离它左边最近的第一个小于它的元素。我们将这个元素左边的全部元素放入栈中，比如我们需要找第i个元素 $a_{i}$ 的左边第1个小于它的元素，那么如果 $a_{i-1} >= a_{i}$ ，那么 $a_{i-1}$ 就肯定不可能作为最终的结果被输出，将 $a_{i-1}$ 出栈。然后我们接着找 $a_{i-2}$ ，接着比较如果 $a_{i-2}\geqslant a _{i}$ ，再将 $a_{i-2}$ 出栈，直到找到一个小于 $a_{i}$ 的值，退出循环。

如果此时栈是空栈，就说明没有一个值是小于 $a_{i}$ 的，打印-1；如果栈不是空栈，此时栈顶元素就是 $a_{i}$ 的左边第一个小于它的值。

下面是样例3 4 2 7 5过程中栈中数据的模拟过程：

图2.2模拟一

图 2.3模拟二

图2.4模拟三

图2.5模拟四

图2.6模拟五

        for(int i = 0;i < n;i++){
            int x = sc.nextInt();
            //将x左边大于等于x的元素出栈
            while (top != -1 && stack[top] >= x){
                top--;
            }
            //栈不为空，此时栈顶元素就是x的左边第一个小于x的值
            if(top != -1){
                pw.print(stack[top]+" ");
            }
            //栈为空，说明x的左边不存在小于x的值
            else {
                pw.print(-1+" ");
            }
            //将x入栈
            stack[++top] = x;
        }

通过上述操作，我们每个元素最多入栈和出栈1次，最终的时间复杂度也就是O(n)。

3.单调递增栈和单调递减栈🌙

单调递增栈：在保持栈内元素单调递增的前提下（如果栈顶元素大于要入栈的元素，将将其弹出），将新元素入栈。

单调递减栈：在保持栈内元素单调递减的前提下（如果栈顶元素小于要入栈的元素，则将其弹出），将新元素入栈。

三、代码如下☀

1.代码如下（示例）：🌙

import java.io.*;
import java.util.*;

public class 单调栈 {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N = 100010;
    static int[] stack = new int[N];
    static int top = -1;
    public static void main(String[] args) {
        Scanner sc = new Scanner(br);
        int n = sc.nextInt();
        for(int i = 0;i < n;i++){
            int x = sc.nextInt();
            while (top != -1 && stack[top] >= x){
                top--;
            }
            if(top != -1){
                pw.print(stack[top]+" ");
            }else {
                pw.print(-1+" ");
            }
            stack[++top] = x;
        }

        pw.flush();
    }
}