题目描述
给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。
输入格式
第一行包含整数N,表示数列长度。
第二行包含N个整数,表示整数数列。
输出格式
共一行,包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。
数据范围
1≤N≤105
1≤数列中元素≤109
输入样例:
5
3 4 2 7 5
输出样例:
-1 3 -1 2 2
求关注~~~
思路
单调栈的思想是利用不断迭代的方式,将当前的元素x与栈顶元素进行比较,按照单调性性质来决定是对栈顶元素做出栈操作还是将当前元素压栈来保证栈的单调性
有一个隐藏的性质,如果是单调递增,如果左边有比当前x还大的数,可以通过单调栈找出离当前x位置最近的较小点位置(也可以说是第一个小的位置值)
一行包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。
因为是找左边第一个小的数,其符合栈的特性,先对后插入的节点进行查找,即后进先出。这完全符合单调栈的性质
举例
初始化栈的tt = 0, 存储位置从1开始, 当tt = 0的时候栈为空,主要方便写if(tt) print(empty)
stack = [], 因为找比当前值x小的元素,所以要保证stack单调递增。
3 4 2 7 5
3:
栈中为空, 输出-1, stack[tt+1] = stack[1] = 3 stack = [3]
4:
3 < 4 输出3 , stack[tt+1] = stack[2] = 4 stack = [3, 4]
2:
2 < 4 4出栈 , tt - 1 = 1 stack = [3] (实际stack = [3, 4])
2 < 3 3出栈 , tt - 1 = 0(栈空) stack = [] (实际stack = [3, 4])
栈中为空 输出-1, stack[tt+1] = stack[1] = 2 stack = [2] (实际stack = [2, 4])
7:
7 > 2 输出2 , stack[tt+1] = stack[2] = 7 stack = [2, 7]
5:
7 > 5 7出栈 , tt - 1 = 1 stack = [2] (实际stack = [2, 7])
5 > 3 输出2 , tt + 1 = 2 stack = [2, 5]
我们在操作的过程,栈中元素一直保持单调性
int x;
scanf("%d", &x);
while(tt && stack[tt] >= x) tt --; // tt > 0 表示栈内有元素,并且栈顶元素大于等于当前值x
if(tt) printf("%d ", stack[tt]); // 栈不为空,意味着栈中栈顶元素小于当前值x
else printf("-1 "); // 栈为空,意味着栈中所有元素都大于等于当前值x
stack[++ tt] = x;
java
import java.util.*;
public class Main{
static int m;
static int N = 100010;
static int[] stack = new int[N];
static int tt = 0;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
while(m -- > 0){
int x;
x = sc.nextInt();
while(tt != 0 && stack[tt] >= x) tt --;
if(tt != 0) System.out.print(stack[tt] + " ");
else System.out.print("-1 ");
stack[++ tt] = x;
}
}
}
python3
N = 100010
stack = [0] * N
tt = 0
def main():
global stack, tt
input()
s = list(map(int, input().rstrip().split(" ")))
for i in range(len(s)):
x = s[i]
while(tt != 0 and stack[tt] >= x): tt -= 1
if(tt != 0): print(stack[tt], end=" ")
else: print("-1", end=" ")
tt += 1
stack[tt] = x
main()
c++
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int stack[N], tt; //tt = 0的时候,栈为空,区别于前面模拟栈,数据填充从1开始
int main(){
scanf("%d", &n);
while(n --){
int x;
scanf("%d", &x);
while(tt && stack[tt] >= x) tt --;
if(tt) printf("%d ", stack[tt]);
else printf("-1 ");
stack[++ tt] = x;
}
return 0;
}
举例那部分是不是2 < 4 和 2 < 3
enen,是的