题解思路

这道题目要求我们计算每个同学能看到的同学总数，也就是计算队列的整齐程度。可以使用单调栈来解决这个问题。

思路分析

对于每个同学，我们需要知道他能看到的所有同学。具体来说，同学$i$能看到他右边的所有比他矮的同学，直到遇到比他高的同学或者遇到队列的末尾。

为了解决这个问题，我们可以使用单调栈来维护一个递减的栈。通过栈来记录每个同学的高度，以及他能看到的同学数目。

解题步骤

1. 遍历每个同学：从右往左遍历每个同学。
2. 栈的操作：对于每个同学，栈中的元素代表了一个能影响当前同学视线的“障碍物”：
   • 如果栈顶的同学比当前同学矮，那么这个同学能看到栈顶同学，并且可以把栈顶同学移除。
   • 如果栈顶的同学比当前同学高或相等，那么这个同学的视线被栈顶同学遮挡，他无法看到更远的同学。
3. 计算视线数量：对于每个同学来说，我们计算他能看到的同学数量，即从当前同学到栈顶的距离。
4. 更新栈：每处理完一个同学后，将该同学的索引压入栈中。

时间复杂度

由于每个同学的索引最多入栈和出栈一次，因此时间复杂度为O(N)。

空间复杂度

我们使用栈来保存同学的索引，因此空间复杂度为O(N)。

代码实现

Python代码

n = int(input())  # 输入同学人数
h = list(map(int, input().split()))  # 输入同学的身高列表

stack = []  # 用来存储身高索引的栈
total = 0  # 用来累加视线数量

# 从右往左遍历每个同学
for i in range(n - 1, -1, -1):
    # 移除栈中比当前同学矮的同学
    while stack and h[stack[-1]] < h[i]:
        stack.pop()
    
    # 如果栈不为空，栈顶的同学是第一个比当前同学高的同学
    if stack:
        cnt = stack[-1] - i  # 当前同学能看到的同学数量
    else:
        cnt = n - 1 - i  # 当前同学能看到所有在他右边的同学
    
    total += cnt  # 累加总的视线数量
    
    stack.append(i)  # 将当前同学的索引加入栈中

print(total)  # 输出最终结果

JAVA代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 输入同学人数
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();  // 输入同学的身高
        }

        Stack<Integer> stack = new Stack<>();  // 用来存储身高索引的栈
        long total = 0;  // 用来累加视线数量

        // 从右往左遍历每个同学
        for (int i = n - 1; i >= 0; i--) {
            // 移除栈中比当前同学矮的同学
            while (!stack.isEmpty() && h[stack.peek()] < h[i]) {
                stack.pop();
            }

            // 如果栈不为空，栈顶的同学是第一个比当前同学高的同学
            long cnt = 0;
            if (!stack.isEmpty()) {
                cnt = stack.peek() - i;
            } else {
                cnt = n - 1 - i;  // 当前同学能看到所有在他右边的同学
            }

            total += cnt;  // 累加总的视线数量

            stack.push(i);  // 将当前同学的索引加入栈中
        }

        System.out.println(total);  // 输出最终结果
    }
}

C++代码

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;  // 输入同学人数
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];  // 输入同学的身高
    }

    stack<int> st;  // 用来存储身高索引的栈
    long long total = 0;  // 用来累加视线数量

    // 从右往左遍历每个同学
    for (int i = n - 1; i >= 0; i--) {
        // 移除栈中比当前同学矮的同学
        while (!st.empty() && h[st.top()] < h[i]) {
            st.pop();
        }

        // 如果栈不为空，栈顶的同学是第一个比当前同学高的同学
        long long cnt = 0;
        if (!st.empty()) {
            cnt = st.top() - i;
        } else {
            cnt = n - 1 - i;  // 当前同学能看到所有在他右边的同学
        }

        total += cnt;  // 累加总的视线数量

        st.push(i);  // 将当前同学的索引加入栈中
    }

    cout << total << endl;  // 输出最终结果
    return 0;
}

题目内容

$N$个同学排成一列，最理想的情况是按身高从小到大排列，这样每个人的视线都不会被遮挡，可以看到他前面的所有人。但由于同学们没有那么听话，可能会出现高个子同学排在前面的情况，导致后面的同学视线被遮挡。

多多想用一个指标来衡量队列的整齐程度:每个同学能看到的同学的总数，这个值越大，说明队列越整齐。请你帮多多计算一下

具体来说，对于第$1$个同学，如果第$i+1、i+2、i+3$个同学都比他矮，$i+4$个同学比他高(或一样高)，则他能看到$4$个同学，但由于视线被遮挡，第$i+5、i+6...、i+x$个同学都无法再看到(即便第$i+x$的身高比$i+4$高)

输入描述

第一行一个整数N，表示同学的数量$(1<=N<=100000)$

第二行包含$N$个整数$h_1,h_2…,h_n$，表示每个同学的身高$(1<=h_j<=1000000000)$

输出描述

输出一个整数，表示队列的整齐程度:所有同学能看到同学的总数

样例1

输入

6
10 7 4 8 2 1

输出

11

说明

第一名同学(高度为$10$)，能看到其右边五个同学，共$5$个

第二名同学(高度为$7$)，能看到第三、四名同学，共$2$个

第三名同学(高度为$4$)，能看到第四名同学，共$1$个

第四名同学(高度为$8$)，能看到第五、六名同学，共$2$个

第五名同学(高度为$2$)，能看到第六名同学，共$1$个

总共$5+2+1+2+1=11$