关注
第三题我完全参考了檐之同学的思路,可以把算法复杂度从O(n2)降到O(n)。附上原作者的链接:https://www.nowcoder.com/discuss/226305?type=post&order=time&pos=&page=1 申请两个数组,lookBackward[i]表示向坐标递减的方向看时,在i位置能看到的楼的个数;lookForward[i]表示向坐标递增的方向看时,在i位置能看到的楼的个数。用栈的size记录楼的个数,若栈顶楼高小于等于当前遍历到的楼高则pop栈顶,否则直接push新楼。 很巧妙的地方是,计算lookBackward数组时从前往后遍历,计算lookForward数组时从后向前遍历,这样刚刚分析的逻辑才成立。最后记得算上当前楼,输出+1。代码如下: import java.util.Scanner;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
int[] lookBackward = new int[n];
int[] lookForward = new int[n];
int[] results = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(nums[0]);
for(int i = 1; i < n; i++){
lookBackward[i] = stack.size();
if(!stack.isEmpty() && nums[i] >= stack.peek()){
stack.pop();
}
stack.push(nums[i]);
}
stack.clear();
stack.push(nums[n-1]);
for(int i = n-2; i >= 0; i--){
lookForward[i] = stack.size();
if(!stack.isEmpty() && nums[i] >= stack.peek()){
stack.pop();
}
stack.push(nums[i]);
}
for(int i=0; i < n; i++){
results[i] = lookBackward[i] + lookForward[i] + 1;
System.out.print(results[i] + " ");
}
}
}
查看原帖
点赞 3
相关推荐

点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 秋招什么时候开投比较合适? #
23701次浏览 318人参与
# 百度工作体验 #
223389次浏览 1972人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
27957次浏览 216人参与
# 机械人与华为的爱恨情仇 #
117155次浏览 946人参与
# 发工资后,你做的第一件事是什么 #
68154次浏览 229人参与
# 机械人集合!你是什么工程师? #
15805次浏览 89人参与
# 你觉得实习能学到东西吗 #
36307次浏览 712人参与
# 找不到好工作选择GAP真的丢人吗 #
78265次浏览 938人参与
# 我想去国央企的原因 #
59993次浏览 393人参与
# 如何准备秋招 #
20667次浏览 390人参与
# 工作中哪个瞬间让你想离职 #
25909次浏览 177人参与
# 入职第四天,心情怎么样 #
29451次浏览 417人参与
# 拼多多工作体验 #
28540次浏览 197人参与
# 多益网络求职进展汇总 #
29228次浏览 134人参与
# 快手求职进展汇总 #
547098次浏览 6001人参与
# 硬件应届生薪资是否普遍偏低? #
74083次浏览 514人参与
# 不考虑转正,实习多久合适 #
32324次浏览 145人参与
# 面试中,你被问过哪些奇葩问题? #
68553次浏览 796人参与
# 你们公司几号发工资 #
21227次浏览 140人参与
# 如果再来一次,你还会学硬件吗 #
125786次浏览 1402人参与
# 实习,不懂就问 #
46386次浏览 693人参与