用c++的单调队列或单调栈完成这道题:输入一组数,我们定义每个数左侧比该数小的最接近该数的数为“相似数”,请编程找出一组数中每个数的“相似数”的值(如果没有符合条件的数,请输出 00)。
时间: 2024-02-13 22:01:40 浏览: 54
好的,这道题可以使用单调栈来解决。
具体做法是,从左往右扫描每个数,将它和它的下标存储为一个元素,然后将其加入到单调栈中。单调栈中的元素从栈底到栈顶按数值递增。每当加入一个新的元素时,就从栈顶开始弹出元素,直到栈顶元素的数值大于等于当前元素的数值,这些被弹出的元素就是当前元素的“相似数”,其中最后一个被弹出的元素就是当前元素左侧比它小的最接近的数。如果所有元素都被弹出了,说明没有符合条件的数,输出 "00"。
下面是 C++ 实现的代码:
```c++
#include <iostream>
#include <stack>
using namespace std;
const int MAXN = 10005;
int a[MAXN], ans[MAXN];
int main() {
int n;
cin >> n;
stack<pair<int, int>> st; // 存储数值和下标的元素
for (int i = 0; i < n; i++) { // 从左往右扫描每个数
cin >> a[i];
int idx = i;
while (!st.empty() && st.top().first < a[i]) { // 弹出栈顶元素
idx = st.top().second;
st.pop();
}
if (st.empty()) { // 没有符合条件的数
ans[i] = 0;
} else { // 最后一个被弹出的元素就是当前元素左侧比它小的最接近的数
ans[i] = st.top().first;
}
st.push({a[i], idx}); // 将当前元素加入到单调栈中
}
for (int i = 0; i < n; i++) { // 输出每个数的“相似数”的值
if (ans[i] == 0) {
cout << "00";
} else {
printf("%02d", ans[i]);
}
if (i < n - 1) {
cout << " ";
}
}
return 0;
}
```
这里使用了一个 pair 类型的元素来存储数值和下标,这样可以方便地在单调栈中存储元素。输出时需要注意,如果输出的数值小于 10,需要在前面补上一个 0。
阅读全文