众所周知,太行山是一片山(而不是一座山)。假设这些山排成了一排。每座山有各自的高度。现在游客们从最左边看山,有些山因为高度没有它左边的某座山高,就会被遮住,游客们就无法看到。现在想请你告诉游客,他能看到几座山。(看到山顶即可被认为是看到了,如果恰好山顶被遮住了,这座山不算被看到)用c语言实现
时间: 2023-08-19 09:03:49 浏览: 95
可以使用单调栈来解决这个问题。
具体思路如下:
1. 从左到右遍历每座山,如果当前山比栈顶元素高,则入栈。
2. 如果当前山比栈顶元素低,则不断弹出栈顶元素直到栈顶元素比当前山高,然后将当前山入栈。
3. 每次入栈都记录一下当前栈的大小,也就是能看到的山的数量。
代码如下:
```c
#include <stdio.h>
#define MAX_N 1000005
int h[MAX_N]; // 存储每座山的高度
int stk[MAX_N]; // 存储单调栈
int top = -1; // 栈顶指针
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &h[i]);
}
int ans = 0;
for (int i = 0; i < n; i++) {
while (top >= 0 && h[i] >= h[stk[top]]) {
top--;
}
ans++;
stk[++top] = i;
}
printf("%d\n", ans);
return 0;
}
```
注意,这里的单调栈是存储的下标而不是高度,这样可以方便地计算能看到的山的数量。
相关问题
众所周知,太行山是一片山(而不是一座山)。假设这些山排成了一排。每座山有各自的高度。现在游客们从最左边看山,有些山因为高度没有它左边的某座山高,就会被遮住,游客们就无法看到。现在想请你告诉游客,他能看到几座山。(看到山顶即可被认为是看到了,如果恰好山顶被遮住了,这座山不算被看到)
这是一道典型的单调栈应用题。我们可以从左到右遍历每座山,用一个栈来维护我们能够看到的山。具体实现如下:
1. 定义一个栈,用来存储每座山的高度。
2. 从左到右遍历每座山,对于每座山执行以下操作:
a. 如果栈为空,将该山的高度入栈。
b. 如果栈不为空,判断该山的高度是否大于栈顶元素的高度。
1) 如果大于栈顶元素的高度,说明该山能被看到,将该山的高度入栈。
2) 如果小于等于栈顶元素的高度,说明该山被遮挡了,将该山的高度舍去。
3. 遍历结束后,栈中元素的个数即为游客能够看到的山的数量。
下面是使用 Python 实现的代码:
```python
def count_visible_mountains(heights):
stack = []
count = 0
for h in heights:
while stack and h >= stack[-1]:
stack.pop()
stack.append(h)
count = len(stack)
return count
```
其中,`heights` 是一个列表,表示每座山的高度。
你好,我准备去安阳玩,可以给我出一份攻略么
当然可以,以下是安阳旅游攻略:
1. 安阳博物馆:安阳博物馆是安阳市内最著名的景点之一,它是中国第一座古代文化遗址博物馆。里面收藏了大量商周时期的文物,如商朝的青铜器、玉器、陶器等。
2. 伏羲庙:伏羲庙是安阳市内最大的古建筑之一,它是为了纪念中国传说中的五帝之一伏羲而建立的。庙内收集了大量的伏羲相关的文物和历史资料。
3. 神农架:神农架是安阳市内的一处自然风景区,它是中国著名的景点之一。景区内有大量的自然景观,如森林、山峰、溪流、瀑布等。游客可以在这里进行徒步旅行、观光、拍照等活动。
4. 豫北民俗博物馆:豫北民俗博物馆是安阳市内的一处博物馆,里面展示了大量的民俗文化和传统手工艺品。游客可以在这里了解到中国传统文化的精髓和历史变迁。
5. 安阳南湖公园:安阳南湖公园是安阳市内最著名的公园之一,它是一个充满活力和美景的地方。公园内有大量的花卉和树木,游客可以在这里进行散步、拍照、休闲等活动。
6. 安阳市政府广场:安阳市政府广场是安阳市内的一个标志性建筑,它是一个庄严、美丽的地方。广场上有大量的雕塑和花卉,游客可以在这里享受美好的风景和氛围。
7. 安阳市文化艺术中心:安阳市文化艺术中心是安阳市内的一处文化场所,里面有大量的文艺表演和展览。游客可以在这里欣赏到中国传统文化和现代艺术的交融之美。
8. 安阳市太行山国家森林公园:安阳市太行山国家森林公园是安阳市内的一处自然风景区,它是中国著名的景点之一。公园内有大量的自然景观,如森林、山峰、溪流、瀑布等。游客可以在这里进行徒步旅行、观光、拍照等活动。
以上是我为您提供的安阳旅游攻略,希望对您有所帮助。
阅读全文