N个同学排成一列,最理想的情况是按身高从小到大排列,这样每个人的视线都不会被遮挡,可以看到他前面的所有人。但由于同学们没有那么听话,可能会出现高个子同学排在前面的情况,导致后面的同学视线被遮挡。
多多想用一个指标来衡量队列的整齐程度:每个同学能看到的同学的总数,这个值越大,说明队列越整齐。请你帮多多计算一下
这道题目要求我们计算每个同学能看到的同学总数,也就是计算队列的整齐程度。可以使用单调栈来解决这个问题。
对于每个同学,我们需要知道他能看到的所有同学。具体来说,同学i能看到他右边的所有比他矮的同学,直到遇到比他高的同学或者遇到队列的末尾。
为了解决这个问题,我们可以使用单调栈来维护一个递减的栈。通过栈来记录每个同学的高度,以及他能看到的同学数目。