Leetcode-monotonic-queue总结

很不擅长的一部分内容，值得总结一下
monotonic queue的应用有
1.求previous less element(PLE), next greater element(NLE), previous greater element(PGE), next greater element(NGE)。以求PGE为例，有两种方式：

1. 从前往后扫，维护一个decreasing monotonic queue

public int[] PGE(int[] nums) {    int[] res = new int[nums.length];    Arrays.fill(res, nums.length); // nums.length表示不存在NGE    Stack<Integer> s = new Stack<>();    for (int i = 0; i < nums.length; i ++) {        while (!s.isEmpty() && nums[i] > nums[s.peek()])            res[s.pop()] = i;        s.push(i);    }    return res;}

1. 从后往前扫，维护一个decreasing monotonic queue

public int[] PGE(int[] nums) {    int[] res = new int[nums.length];    Arrays.fill(res, nums.length);    Stack<Integer> s = new Stack<>();    for (int i = nums.length-1; i >= 0; i --) {        while (!s.isEmpty() && nums[s.peek()] <= nums[i])            s.pop();        if (!s.isEmpty())    res[i] = s.peek();        s.push(i);    }    return res;}