PDD筆試（20250325）——身高排序
題目?jī)?nèi)容
N個(gè)同學(xué)排成一列，最理想的情況是按身高從小到大排列，這樣每個(gè)人的視線都不會(huì)被遮擋，可以看到他前面的所有人。但由于同學(xué)們沒有那么聽話，可能會(huì)出現(xiàn)高個(gè)子同學(xué)排在前面的情況，導(dǎo)致后面的同學(xué)視線被遮擋。多多想用一個(gè)指標(biāo)來(lái)衡量隊(duì)列的整齊程度:每個(gè)同學(xué)能看到的同學(xué)的總數(shù)，這個(gè)值越大，說(shuō)明隊(duì)列越整齊。請(qǐng)你幫多多計(jì)算一下
具體來(lái)說(shuō)，對(duì)于第1個(gè)同學(xué)，如果第i+ 1、i+ 2、i+ 3個(gè)同學(xué)都比他矮，i+ 4個(gè)同學(xué)比他高(或一樣高)，則他能看到4個(gè)同學(xué)，但由于視線被遮擋，第i+ 5、i+ 6..、i+ r個(gè)同學(xué)都無(wú)法再看到(即便第i+ z的身高比i + 4高)
單調(diào)?？山猓?/p>
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()]) //當(dāng)前元素大于棧頂元素，則彈出棧頂元素
st.pop();
if (!st.isEmpty() && hight[i] == hight[st.peek()]) //當(dāng)前元素等于棧頂，則只算1人
res[i] = st.peek() - i;
else if(!st.isEmpty()) //當(dāng)前元素小于棧頂元素，則計(jì)算差值
res[i] = st.peek() - i;
else //?？眨瑒t從當(dāng)前元素到默認(rèn)都計(jì)入
res[i] = (num- 1) - i ;
st.push(i);
}
System.out.println(Arrays.stream(res).sum());
}
}
}