AcWing 830. 单调栈

# 单调栈

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int stk[N], tt;

int main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x
		while(tt && stk[tt] >= x) tt--;
		if(tt) cout << stk[tt] << ' ';
		else cout << -1 << ' ';
		stk[++tt] = x;
	}
	return 0;
}

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int stk[N], tt;

int main(){
    //第一种优化
    ios::sync_with_stdio(false);//-300ms
    
    //第二种优化
    cin.tie(0);
    //差不多和scanf一样
    //如果用scanf printf的话会快十倍 比加了sync还快十倍
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        while(tt && stk[tt] >= x) tt--;
        //如果栈顶即stk[tt] >= x 就是永远不会用到了所以 tt--
        if(tt) cout << stk[tt] << ' ';
        //如果tt还是存在那么这个栈顶元素就是离i最近的左边第一个比它小的数 输出就可以了
        else cout << -1 << ' ';
        
        stk[++tt] = x;
        //最后要记得把x插到栈里去
    }
    
    return 0;
}