共计 717 个字符,预计需要花费 2 分钟才能阅读完成。
很不擅长的一部分内容,值得总结一下
monotonic queue 的应用有
1. 求 previous less element(PLE), next greater element(NLE), previous greater element(PGE), next greater element(NGE)。以求 PGE 为例,有两种方式:
- 从前往后扫,维护一个 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; | |
} |
- 从后往前扫,维护一个 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; | |
} |
正文完