给出代码用c++的单调队列或单调栈完成这道题:午饭时间到了,同学们到食堂的窗口前排好了队伍,排队时间太长了,张同学无聊之际想到了一个问题,如果要编一个程序,输入每个人的身高(从最后一个同学开始输入,一直到排在第 11 位的挨着打菜窗口的同学,按照这个顺序输入),计算出每个人的前面能看到几个人,应该如何解决呢? 请注意:一个同学能够看到的人是在他前面且身高严格低于他的人,并且他的视线会被在他前面第一个身高大于等于他的人挡住。也就是说无论如何也无法看到再前面的人。
时间: 2023-12-11 07:04:14 浏览: 66
好的,下面是使用单调栈实现的 C++ 代码:
```c++
#include <iostream>
#include <stack>
using namespace std;
const int MAXN = 10005;
int h[MAXN], ans[MAXN];
int main() {
int n = 0;
stack<pair<int, int>> st; // 存储身高和下标的元素
while (n < 11) { // 读入前11个同学的身高
cin >> h[n++];
}
for (int i = n - 1; i >= 0; i--) { // 从后往前扫描每个同学的身高
int cnt = 0; // 当前同学能够看到的人数
while (!st.empty() && st.top().first < h[i]) { // 弹出栈顶元素
cnt++;
st.pop();
}
if (!st.empty()) { // 能够看到的人中,最前面的一个身高大于等于当前同学的身高
cnt++;
}
st.push({h[i], i}); // 将当前同学加入到单调栈中
ans[i] = cnt;
}
for (int i = n - 1; i >= 0; i--) { // 输出每个同学能够看到的人数
cout << ans[i] << endl;
}
return 0;
}
```
这里使用了一个 pair 类型的元素来存储身高和下标,这样可以方便地在单调栈中存储元素。
阅读全文