郊游
题目描述
摩乐乐和他的朋友想出去郊游，他们现在有n座山（排成一行）可以选择，并且每座山的山顶都有独一无二的风景。当爬上某座山的山顶时，除了可以欣赏这座山本身的风景，还可以欣赏其他山顶的风景(只能看到比这座山高的风景，且因为视野影响可能只能看到高度单调递增的地方)。现在给出n座山的高度，请计算出爬上每座山的可以欣赏的风景的数量供摩乐乐和他的朋友选择。
输入格式
第一行 一个整数n
第二行 n个整数 a1…n表示每座山的高度
输出格式
一行n个整数 表示每座山可以看到的风景数量
数据规模
1＜＝n＜＝1e5
1＜＝ai＜＝1e9
输入样例
6
5 4 4 1 3 4
输出样例
1 2 2 5 4 2
样例解释
每座山可以看到的风景：
1: 1
2: 1 2
3: 1 3
4: 1 3 4 5 6
5: 1 3 5 6
6: 1 6
【以下回答由 GPT 生成】
我们可以使用一个栈来解决这个问题。遍历每座山的高度，然后将高度依次入栈。在入栈之前，需要判断当前山的高度是否大于栈顶的山高度，如果是，则将栈中所有高度小于当前山高度的山弹出，并且记录弹出山的风景数量。
具体步骤如下：
下面是使用C语言实现的代码：
#include <stdio.h>
#define MAX_SIZE 100000
typedef struct {
int height; // 山的高度
int scenery; // 可看到的风景数量
} Mountain;
typedef struct {
Mountain data[MAX_SIZE];
int top; // 栈顶指针
} Stack;
void initStack(Stack *s) {
s->top = -1;
}
void push(Stack *s, Mountain m) {
s->top++;
s->data[s->top] = m;
}
Mountain pop(Stack *s) {
Mountain m = s->data[s->top];
s->top--;
return m;
}
int main() {
int n;
scanf("%d", &n);
Stack stack;
initStack(&stack);
for (int i = 0; i < n; i++) {
Mountain m;
scanf("%d", &m.height);
m.scenery = 1;
while (stack.top >= 0 && m.height >= stack.data[stack.top].height) {
m.scenery += stack.data[stack.top].scenery;
pop(&stack);
}
if (stack.top >= 0) {
m.scenery++; // 当前山除了能看到比它高的山外，还能看到当前出栈的山
}
push(&stack, m);
printf("%d ", m.scenery);
}
return 0;
}
这段代码首先定义了两个结构体：Mountain 用于存储山的高度和对应的风景数量，Stack 用于实现栈的数据结构。
然后定义了几个函数：initStack 用于初始化栈，push 用于入栈，pop 用于出栈。
在 main 函数中，先读入山的个数 n，然后初始化栈，并通过循环遍历每座山的高度。
在循环中，首先读入当前山的高度，并设置初始的风景数量为1。然后判断当前山的高度是否大于栈顶的山高度，如果是，则将栈中所有高度小于当前山高度的山弹出，并且累加风景数量。如果栈非空，还需要再加1，因为除了能看到比当前山高的山外，还能看到当前出栈的山。
最后将当前山的高度和风景数量入栈，并输出风景数量。
最终输出的就是每座山对应的风景数量。
【相关推荐】