谁挡住了我的红绿灯

单调栈

思路并不难想，用单调栈来做，可以理解为构建一个“小压大”的单调栈。栈不为空，且当前元素直接压入会破坏单调性时（栈顶车辆不会挡住当前车辆的视线）进行弹栈。

那么如何判断车辆会遮挡车辆的视线呢？需要一些数学方法。

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        int h = Integer.parseInt(params[1]);
        params = br.readLine().split(" ");
        int[] heights = new int[n + 1];
        heights[0] = h;
        for(int i = 0; i < n; i++){
            heights[i + 1] = Integer.parseInt(params[i]);
        }
        int[] res = new int[n + 1];
        Stack stack = new Stack();
        for(int i = 1; i <= n; i++){
            while(!stack.isEmpty() && check(stack, heights, i, h)){
                int top = stack.pop();
                res[top] = stack.isEmpty()? 0: stack.peek();
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            res[stack.pop()] = stack.isEmpty()? 0: stack.peek();
        }
        for(int i = 1; i <= n; i++){
            System.out.println(res[i]);
        }
    }

    private static boolean check(Stack stack, int[] heights, int i, int h) {
        int j = stack.peek();
        return (long)i * heights[j] < (heights[i] - h) * (long)j + (long)h*i;
    }
}

讲道理已经是O(N)的时间复杂度了，但一直过不了。这个题卡时间卡得有点无语，改成C++还会卡打印API的时间，离离原上谱，知道思路就好了吧。