PDD笔试（20250325）——身高排序

题目内容

N个同学排成一列，最理想的情况是按身高从小到大排列，这样每个人的视线都不会被遮挡，可以看到他前面的所有人。但由于同学们没有那么听话，可能会出现高个子同学排在前面的情况，导致后面的同学视线被遮挡。多多想用一个指标来衡量队列的整齐程度:每个同学能看到的同学的总数，这个值越大，说明队列越整齐。请你帮多多计算一下

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

单调栈可解：

import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] hight = new int[num];
        ArrayDeque<Integer> st = new ArrayDeque<>();
        for(int i = 0; i < num; ++i){
            hight[i] = sc.nextInt();
        }

        int[] res = new int[num];
        for (int i = num-1; i >= 0; --i){
            while (!st.isEmpty() && hight[i] > hight[st.peek()])    //当前元素大于栈顶元素，则弹出栈顶元素
                st.pop();
            if (!st.isEmpty() && hight[i] == hight[st.peek()])  //当前元素等于栈顶，则只算1人
                res[i] = st.peek() - i;
            else if(!st.isEmpty())      //当前元素小于栈顶元素，则计算差值
                res[i] = st.peek() - i;
            else        //栈空，则从当前元素到默认都计入
                res[i] = (num- 1) - i ;
            st.push(i);
        }
        System.out.println(Arrays.stream(res).sum());
    }
}

}