第三题我完全参考了檐之同学的思路，可以把算法复杂度从O(n²)降到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] + " ");
        }
    }
}

15959	小Q的歌单	2019-08-17	答案正确	7ms	1292K	C++	题解
15959	小Q的歌单	2019-08-17	答案正确	5ms	1248K	C++	题解
15959	小Q的歌单	2019-08-17	答案正确	5ms	488K	C++	题解
15957	纸牌游戏	2019-08-17	答案正确	89ms	1892K	C++	题解
15956	翻转数列	2019-08-17	答案正确	5ms	496K	C++	题解