本文共 2354 字，大约阅读时间需要 7 分钟。

Bad Hair Day

Some of Farmer John’s N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows’ heads.

Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.

Consider this example:

=

= =

= - = Cows facing right --> = = = = - = = = = = = = = = 1 2 3 4 5 6 Cow#1 can see the hairstyle of cows #2, 3, 4 Cow#2 can see no cow’s hairstyle Cow#3 can see the hairstyle of cow #4 Cow#4 can see no cow’s hairstyle Cow#5 can see the hairstyle of cow 6 Cow#6 can see no cows at all!

Let ci denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.

Input

Line 1: The number of cows, N. Lines 2…N+1: Line i+1 contains a single integer that is the height of cow i. Output Line 1: A single integer that is the sum of c 1 through cN. Sample Input 6 10 3 7 4 12 2 Sample Output 5

感觉就是个单调栈的模板题，主要是能想到用单调栈，说实话，要不是看见前面有个单调队列的模板题，还真不一定能想到，这方面的题做的属实太少，还是要加油呀。

感觉挂的前后俩题都是单调栈 一开始看样例 10 3 7 4 我还以为7会把4挡住让后10就看不见了，显然不是，如果我这样的错误理解就不用这么麻烦了。但是7却会挡住3，让3看不到后面的，这个时候3就是没有用的了，可以直接去掉，很符合单调栈模型。也就是说： (1)当前高度 >= 栈顶高度的时候，就需要不断的弹出栈顶元素一直到栈顶元素严格大于当前元素。 (2)当前高度 < 栈顶高度的时候，就直接入栈即可。 每次栈中元素个数即为前面能看到当前元素的数量，累加即可。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105959514 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！