首页 > 试题广场 >

枪打出头鸟

[编程题]枪打出头鸟

热度指数：5957 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

现在有n个人站成一列，第i个人的身高为 $a_{i-1}$ 。

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

示例1

输入

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

输出

说明

没有一个人击中任何一个人

示例2

输入

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

输出

说明

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

备注:

一个整数n()
一个数组a()
a下标从0开始，

算法知识视频讲解

钢琴手1720

看评论可能暴力解法能通过，不过还是推荐最标准的单调栈解法，今年四月的腾讯实习机试有一道一摸一样的题目，暴力解法超时，就很难受，所以单调栈的解法我真的是记忆深刻！！

class Solution {
public:
    //
    long long solve(int n, vector<int>& a) {
        // write code here
        long long res=0;
        stack<pair<int,int>> S;
        S.push({a[0],1});
        for(int i=1;i<n;i++){
            while(!S.empty()){
                if(S.top().first<=a[i])
                    S.pop();
                else
                    break;
            }
            if(!S.empty())
                res+=S.top().second;
            S.push({a[i],i+1});
        }
        return res;
    }
};

发表于 2020-07-27 08:32:07 回复(0)

lllllllrrrr

思路：

题目的意思就是求离当前结点最近的上一个结点的下标（前提是上一个结点的值比当前结点大）

第一种解法：暴力法

import java.util.*;


public class Solution {
    public long  solve (int n, int[] a) {
        if(n<=1){
            return 0;
        }
        long score=0l;
        for(int i=0;i<n;i++)
            for(int j=i;j>=0;j--){
                if(a[j]>a[i]){
                    score+=j+1;
                    break;
                }
            }
        return score;
    }
}

第二种解法：栈

这种解法要点在于保存每一个结点的下标用于下一个结点的大小比较

假如5，3，2

你不能因为5>3就把3的小标给扔了，会造成5>2，结果保存了5所在的下标

解法缺点：会报运行超时，过不去

import java.util.*;


public class Solution {
    public long  solve (int n, int[] a) {
        if(n<=1){
            return 0;
        }
        // write code here
        Stack<Integer> s=new Stack<>();

        long  score=0l;
        for(int i=0;i<n;i++){
            //寻找到大于当前结点的结点时退出
            while(!s.empty()&&a[s.peek()]<=a[i]){
                s.pop();
            }
            while(!s.empty()){
                score+=s.peek()+1;
            }
            //保存每一个下标
            s.push(i);
        }
        return score;
    }
}

发表于 2020-07-04 23:58:01 回复(2)

C/C++

nbgao

class Solution {
public:
    /**
     * 
     * @param n int整型 n个人
     * @param a int整型vector ai代表第i个人的高度
     * @return long长整型
     */
    long long solve(int n, vector<int>& a) {
        long long s = 0;
        stack<int> S;
        for(int i=0;i<n;i++){
            while(!S.empty() && a[S.top()]<=a[i])
                S.pop();
            if(!S.empty())
                s += S.top()+1;
            S.push(i);
        }
        return s;
    }
};

发表于 2020-07-03 21:15:21 回复(0)

C/C++

寇

class Solution {
public:
long long solve(int n, vector<int>& a) {
if (n <= 1) {
return 0;
}
long long result = 0;
for (int i = 0; i < n; i ++) {
for (int j = i - 1; j >= 0; j --) {
if (a[j] > a[i]) {
result += (j + 1);
break;
}
}
}
return result;
}
};

编辑于 2020-05-10 22:17:38 回复(1)

Python3

在喝茶的咸鱼很温柔

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

# @param n int整型 n个人

# @param a int整型一维数组 ai代表第i个人的高度

# @return long长整型

class Solution:

def solve(self, n, a):

# write code here

stack = [0]

for i in range(n - 1, 0, -1):

for j in range(i - 1, -1, -1):

if a[i] < a[j]:

stack.append(j + 1)

break

sum = 0

for x in stack:

sum += x

return sum

发表于 2022-12-09 11:50:17 回复(0)

前端UI-一条帅龙

long long solve(int n, int* a, int aLen ) {
// write code here
long long int sum=0;//荒唐度
if(n>1)
{
for(int j=1;j<n;j++)
{
for(int i=j-1;i>=0;i--)
{
if(a[i]>a[j])
{
sum+=i+1;
break;
}
}
}
return sum;

}
else
return NULL;
}

发表于 2022-05-18 22:37:45 回复(0)

天界人

这题写的用栈，结果比暴力浪费空间，时间还慢。。。
用栈的代码如下：

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 n个人
     * @param a int整型一维数组 ai代表第i个人的高度
     * @return long长整型
     */
    public long solve (int n, int[] a) {
        // write code here
        Stack<Integer> s = new Stack<>();
        Map<Integer,Integer> map =new HashMap<>();
        if(n<=1){
            return 0;
        }
        long res = 0;
        s.add(a[0]);
        map.put(a[0],1);
        for (int i=1;i<n;i++){
            while (!s.isEmpty()&&a[i]>=s.peek()){
                s.pop();
            }
            if (s.isEmpty()){
                s.add(a[i]);
                map.put(a[i],i+1);
            }else {
                res+=map.get(s.peek());
                s.add(a[i]);
                map.put(a[i],i+1);
            }
        }
        return res;
    }
}

发表于 2020-08-10 10:33:33 回复(0)

牛客428477065号

public class Solution {
    /**
     * 
     * @param n int整型 n个人
     * @param a int整型一维数组 ai代表第i个人的高度
     * @return long长整型
     */
    public long solve (int n, int[] a) {
        int max=a[0];
        int index=0;
        long sum=0;
        for(int i=1;i<n;i++){
            if(max<=a[i]){
                //保存当下最高
                max=a[i];
                index=i;
            }else{
                for(int j=i-1;j>=index;j--){
                    if(a[i]<a[j]){
                        sum+=j;
                        //数组下标从0+导致的问题
                        sum++;
                        break;
                    }
                }
            }
        }
        return sum;
    }

发表于 2020-07-29 16:42:09 回复(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)

牛客953075355号

暴力解法：直接判断前面第几个比当下这个高

发表于 2020-07-18 14:27:57 回复(1)

Java

Fubuki_0v0

public class Solution {
/**
*
* @param n int整型 n个人
* @param a int整型一维数组 ai代表第i个人的高度
* @return long长整型
* 用栈，随指针i，只存降序数列(包括指针)，降序存，升序出
* 例如：1254312312
* i: 0123456789
* 1，2，5，54，543，5431，5432，543，5431，5432
* 0，1，2，3 ，4 ，5 ，6 ，7 ，8 ，9
*/
public long solve (int n, int[] a) {
// write code here
if(n<=1) {
return 0;
}
if(n==2) {
return a[0]>a[1] ? 1 : 0;
}
List<Integer> stack = new ArrayList<>();
long j=0;
for(int i=0; i<n; i++) {
while(!stack.isEmpty() && a[i]>=a[stack.get(stack.size()-1)]) {
stack.remove(stack.size()-1);
}
if(!stack.isEmpty()) {
j+=stack.get(stack.size()-1)+1;
}
stack.add(i);
}
return j;
}
}

发表于 2020-07-05 11:48:41 回复(0)

Java

牛短熊长

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 n个人
     * @param a int整型一维数组 ai代表第i个人的高度
     * @return long长整型
     */
    public long solve (int n, int[] a) {
        // write code here
        long ht=0;
        int[] hts=new int[n];
        int pre=0,ppre=0;
        if(n<=1){
            return 0;
        }
        if(a[0]>a[1]){
            ht=1;
            hts[1]=1;
        }
        if(n==2){
            return ht;
        }
        pre=1;
        ppre=hts[pre-1];
        for(int i=2;i<n;i++){
            if(a[i]<a[i-1]){
                hts[i]=i;
            }else{
                pre=i-1;
                while(a[i]>=a[pre]&&(ppre=hts[pre])!=0){
                    if(a[i]<a[ppre-1]){
                        hts[i]=ppre;
                        break;
                    }else{
                        pre=ppre-1;
                    }
                }
            }
            ht+=hts[i];
        }
        return ht;
    }
}

发表于 2020-06-15 23:31:03 回复(1)

Python

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)

Dreambe

class Solution:
    def solve(self , n , a ):
        # write code here
        sum_num = 0
        for i in range(n-1, -1, -1):=
            for j in range(i, -1, -1):
                if a[j] > a[i]:
                    sum_num += j
        return sum_num

发表于 2020-04-21 23:45:40 回复(1)

C/C++

铭字_

class Solution {
public:
/**
*
* @param n int整型 n个人
* @param a int整型vector ai代表第i个人的高度
* @return long长整型
*/
long long solve(int n, vector<int>& a) {
// write code here
if(n != a.size())

return -1;

//题意其实就是找每个元素的前面离它最近且比它本身大的元素的下标。

int i,j;
long long sum=0;
for(i=1;i<n;i++)
{
for(j=i-1;j>=0;j--)
{
if(a[j]>a[i])//找到符合的元素，加上下标+1（表示第几个人），然后继续找下一个元素的目标。
{
sum += j+1;
break;
}
}
}
return sum;
}
};

发表于 2020-04-14 19:43:30 回复(0)

C/C++

牛客382923277号

用数组r表示: 在第i个人的前方，最接近i的比i高的人是r[i]

r[i]=-1表示在其前方没有人比i高

荒唐度为r[i]+1

对于a[i],依次比较a[i-1],r[a[i-1]].r[r[a[i-1]],...

long long solve(int n, vector<int>& a) {
        // write code here
        int len=(int)a.size();
        vector<int> r(len); // 在第i个人d前方，最接近i的比i高的人是r[i]
        r[0]=-1;// -1表示在其前方没有人比a[i]高
        for(int i=1;i<len;i++){
            int j=i-1;
            while(a[i]>=a[j] && j>=0){
                j=r[j];
            }
            r[i]=j;
        }
        long long ans=0;
        for(auto &k : r) ans+=k+1;
        return ans;
    }

提交观点

发表于 2020-04-10 17:44:41 回复(0)