关注
第三题我完全参考了檐之同学的思路,可以把算法复杂度从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
相关推荐
牛客热帖
更多
正在热议
更多
# 风评不好的公司,你会去吗? #
37150次浏览 227人参与
# 假如你的老板掉河里,你的工作能为他做什么 #
31078次浏览 380人参与
# 第一份工作应该选高薪还是热爱? #
70765次浏览 675人参与
# 职场新人体验 #
3054次浏览 50人参与
# 你觉得第一学历对求职有影响吗? #
95281次浏览 674人参与
# 外包能不能当跳板? #
37764次浏览 228人参与
# 你觉得早上几点上班合适? #
73484次浏览 308人参与
# 学历贬值真的很严重吗? #
26088次浏览 179人参与
# 推荐一首陪你工作的歌吧 #
15123次浏览 99人参与
# 秋招签约后的心态变化 #
83787次浏览 820人参与
# 双非能在秋招上岸吗? #
223119次浏览 1180人参与
# 听劝,这个公司值得去吗 #
487446次浏览 1709人参与
# 打工人的工作餐日常 #
54699次浏览 432人参与
# 反问环节如何提问 #
93645次浏览 1938人参与
# 大学最后一个寒假,我想…… #
47290次浏览 576人参与
# 面试被问第一学历差时该怎么回答 #
137778次浏览 853人参与
# 月薪多少能在一线城市生存 #
35790次浏览 352人参与
# 一人推荐一个值得去的通信/硬件公司 #
186975次浏览 1861人参与
# 我想象的实习vs现实的实习 #
288329次浏览 2244人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
93164次浏览 686人参与