Nearest Smaller Values(sorting and searching)

题目描述

Given an array of n integers, your task is to find for each array position the nearest position to its left having a smaller value.

输入

The first input line has an integer n: the size of the array.
The second line has n integers x1,x2,...,xn: the array values.
Constraints
1 ≤ n ≤ 
1 ≤ xi ≤ 

输出

Print n integers: for each array position the nearest position with a smaller value. If there is no such position, print 0.

样例输入

8
2 5 1 4 8 3 2 5

样例输出

0 1 0 3 4 3 3 7

思路分析

1.输入处理：首先读取数组大小n，然后读取数组arr。

2.初始化：res数组用于存储结果，初始化为0（表示没有找到符合条件的元素）。stack用于维护单调递增的索引栈。

3.单调栈处理：

遍历数组中的每个元素。

当栈非空且栈顶索引对应的元素值大于等于当前元素值时，弹出栈顶（因为这些元素不可能成为后续元素的答案）。

如果栈非空，栈顶索引对应的元素即为左边最近的小于当前元素的值，将其索引（加1转换为1-based）存入res[i]。

将当前索引压入栈中。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,x;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;vector<int>arr(n);for(int i=0;i<n;i++){cin>>arr[i];}vector<int>res(n,0);vector<int>mystack;for(int i=0;i<n;i++){while(!mystack.empty()&&arr[mystack.back()]>=arr[i]){mystack.pop_back();}if(!mystack.empty()){res[i]=mystack.back()+1;}mystack.push_back(i);}for(int i=0;i<n;i++){cout<<res[i]<<" ";}return 0;
}