【单调栈】单调栈「单调栈经典应用」

题目

830. 单调栈

---

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

输入格式

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

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

输出格式

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

数据范围

$1 \le N \le 10^5$
$1 \le 数列中元素 \le 10^9$

输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

解题

方法一：单调栈

思路

一个朴素的做法是对于每一个 $nums[i]$，都遍历 $nums[i - 1 \to 0]$ 找到第一个小于它的数就输出，伪代码：

for i, n in nums:
	for j from i - 1 to 0:
		if nums[j] < n:
			print("{n} ")
			break

用栈的思路来思考就是枚举到 $nums[i]$ 栈中有 $stack(nums[0 \dots i-1])$ ，然后从栈顶开始出栈，直到找到第一个比 $nums[i]$ 小的数输出。

思考一下就会发现栈了有些数是永远都不会被输出的，例如有 $j < i$ 且 $nums[j] \ge nums[i]$，那么对于 $nums[k](k > i)$ 来说就永远不会选到 $nums[j]$ ，因为在离 $k$ 更近的地方有更小的数 $nums[i]$ 用于选择，怎么来说都比 $nums[j]$ 更优。

所以如果栈中出现形如 $nums[j]$ 的元素直接弹出即可，这样就形成了一个单调栈。所以每次往栈中加入元素时都循环地与栈顶元素进行比较，如果栈顶元素大于等于待加入元素就把栈顶元素出栈。删完所有符合条件的栈顶元素后剩下的栈顶元素就是在当前元素左边第一个比它小的数，把它输出并把当前元素加入栈中。

代码

数组模拟栈：

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n;
int stk[N], tt = 0;

int main() {
    scanf("%d", &n);
    while (n--) {
        int x;
        scanf("%d", &x);
        while (tt && x <= stk[tt]) --tt;
        printf("%d ", tt ? stk[tt] : -1);
        stk[++tt] = x;
    }
    
    return 0;
}

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

public class Main {
    static final int N = (int) 1e5 + 10;
    static int tt;
    static int[] stk = new int[N];
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        while (n-- > 0) {
            in.nextToken();
            int x = (int) in.nval;
            while (tt > 0 && stk[tt] >= x) --tt;
            System.out.print(tt == 0 ? "-1 " : stk[tt] + " ");
            stk[++tt] = x;
        }
    }
}

API 栈：

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

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        Deque<Integer> stk = new LinkedList<>();
        while (n-- > 0) {
            in.nextToken();
            int x = (int) in.nval;
            while (!stk.isEmpty() && stk.peek() >= x) stk.pop();
            System.out.print(stk.isEmpty() ? "-1 " : stk.peek() + " ");
            stk.push(x);
        }
    }
}