$$\color{Red}{单调栈 JAVA C++ Python 容器}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思考

这题比较简单，一个指针不断遍历整个数组的过程中，栈维护当前点前的最小点，如果发现遍历到的点比栈顶的大于或等于，就弹出栈顶数字等于也弹出！因为当前点已经成为最小点。

java容器

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {
    static int N = (int)1e5 + 10, n;
    static LinkedList<Integer> stack = new LinkedList<>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        String[]s1 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(s1[i]);
            while(!stack.isEmpty() && stack.peek() >= x) stack.pop();
            if(stack.isEmpty()) System.out.print("-1 ");
            else System.out.print(stack.peek() + " ");
            stack.push(x);
        }
    }
}

java手写栈

import java.util.*;

public class Main {
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int [] stk = new int [100010];
        int tt = 0;

        for (int i=0; i<n; i++) {
            int x = sc.nextInt();

            while (tt!=0 && stk[tt] >= x) tt -= 1;
            if (tt!=0) System.out.print(stk[tt] + " ");
            else System.out.print("-1 ");
            stk[++tt] = x;
        }
    }
}

Python3 代码

N = int(1e5 + 10)
stk = [0] * N
n = input()
a = [int(x) for x in input().split()]
tt = 0
for i in a:
    while tt and stk[tt] >= i:
        tt -= 1
    if(tt == 0):
        print('-1',end=' ')
    else:
        print(stk[tt], end=' ')
    tt += 1
    stk[tt] = i

C++ 代码

#include <iostream>
using namespace std;
const int N = 100010;
int stk[N], tt;

int main()
{
    int n, x;
    cin >> n;
    while(n--)
    {
        scanf("%d", &x);
        //等于号很重要，当前面最小数和当前数相等，应该输出-1
        while(tt !=0 && stk[tt] >= x) tt--;
        if(!tt)  printf("-1 ");
        else     printf("%d ", stk[tt]);
        stk[++tt] = x;
    }
    return 0;
}