首页 > 试题广场 >

枪打出头鸟

[编程题]枪打出头鸟
  • 热度指数：5806 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
现在有n个人站成一列，第i个人的身高为。

他们人手一把玩具枪，并且他们喜欢把枪举在头顶上。
每一次练习射击，他们都会朝正前方发射一发水弹。
这个时候，第i个人射击的水弹，就会击中在他前面第一个比他高的人。
牛牛认为这样的练习十分的荒唐，完全就是对长得高的人的伤害。
于是它定义了一个荒唐度，初始为0。
对于第i个人，如中他击中了第j个人，则荒唐度加j，如果没有击中任何人，则荒唐度加0.
牛牛想问你，你能计算出荒唐度是多少吗？

示例1

输入

5,[1,2,3,4,5]

输出

0

说明

没有一个人击中任何一个人
示例2

输入

5,[5,4,3,2,1]

输出

10

说明

第二个人击中第一个人，第三个人击中第二个人，第四个人击中第三个人，第五个人击中第四个人； 1+2+3+4=10

备注:
一个整数n()
一个数组a()
a下标从0开始，
算法知识视频讲解
添加回答
Python
白色纯度头像 白色纯度
python只能通过百分之40，总是提示复杂度过高，但我感觉思路应该没错的。
一句话，你能把水枪射到你前面第一个严格比你高的人B，可你绝对射不到B身后的任何人。因此对于给定的数组a，从左向右扫描，建立一个递减数字的栈，栈内首个元素可以设置为a的首个元素和位置形成的二元数组（（a[0],0））。扫描过程如下：举例，设a为【3,5,4,8,1,4,9,7,2】
1，维护一个栈compa，初始化为 【（3，0）】
2，从a的第二项开始，从左向右扫描数组，每次都将a数组循环到的数字与compa的尾元素数组第一项进行比较。如果你的身高很高，那么你的水枪是射不到compa尾元素的那个人的，因此需要pass掉这个人，而且由于你的身高高于这个人，那么在你后边的人发射水枪时，你就成了比你矮的人的保护伞。所以从尾至头将compa中的比你低的人删除，直到遇到了比你高的人或者compa为空（即你是当前最高的人）时，此时可以把自己的高度和位置保存到compa中。
3，每当你成功保存在compa中一个元素时，如果compa中有两个及两个以上的元素，那么说明你的水枪成功射到了倒数第二个元素的那个人，如果compa只有一个元素，那么你保存的这个元素就是当前最高的人，无需对结果进行统计累加。 
class Solution:
    def solve(self , n , a ):
        res = 0
        compa = [(a[0],1)]
        for i in range(1,n):
            while compa and a[i]>=compa[-1][0]:
                compa.pop()
            compa.append((a[i],i+1))
            if len(compa)!=1:
                res += compa[-2][-1]
        return res



发表于 2020-07-26 18:54:50 回复(0)
Python
Damocles201810251934668头像 Damocles201810251934668
完全跟c++实现相同的算法，python3超时 
class Solution:
    def solve(self , n , a ):
        stack=[]
        res=0
        for i in range(n):
            while(len(stack) and a[stack[len(stack)-1]]<=a[i]):
                stack.pop()
            if len(stack):
                res = res + stack[len(stack)-1]+1
            stack.append(i)
        return res
发表于 2020-04-24 16:34:29 回复(1)
提交观点

问题信息

栈
难度：
2条回答 4495浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号