题解 | #愤怒的小鸟#

愤怒的小鸟

https://www.nowcoder.com/practice/597c32f0b3cf43beb1d01e7ddd87cc32

单调栈

#include <iostream>
#include <bits/stdc++.h>
#include <stack>
using namespace std;

int main() {
    int n;
    cin>> n;
    vector<int> h(n);
    for(int i=0;i<n;i++){
        cin>> h[i];
    }
    stack<int> stk; // 单调减,保存当前能炸到i的点的个数
    vector<int> res(n);
    for(int i=0;i<n;i++){
        while(!stk.empty()&& h[i]>stk.top()){
            stk.pop();
        }
        res[i] += i - stk.size();
        stk.push(h[i]);
    }
    stk = stack<int>();
    for(int i=n-1;i>=0;i--){
        while(!stk.empty()&&h[i]>stk.top()){
            stk.pop();
        }
        res[i] += (n-1 -i) - stk.size();
        stk.push(h[i]);
    }
    for(int i=0;i<n;i++){
        cout << res[i] << " ";
    }
}
// 64 位输出请用 printf("%lld")

全部评论

相关推荐

zhiyog:哈哈哈哈哈哈哈哈哈哈哈哈哈
点赞 评论 收藏
分享
点赞 评论 收藏
分享
认真搞学习:这么良心的老板真少见
点赞 评论 收藏
分享
看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗?&nbsp;那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务