一、单调栈
单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。
单调栈模板
维护一个单调栈结构：
- 对于每一个元素，对栈进行处理使得加入遍历完成该元素后依然能保持单调性。
- 结果+将该元素存入单调栈中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
vector<int> nextGreaterElement(vector<int>& nums) {
vector<int> res(nums.size()); // 存放答案的数组
stack<int> s;
// 倒着往栈里放
for (int i = nums.size() - 1; i >= 0; i--) {
// 判定个子高矮
while (!s.empty() && s.top() <= nums[i]) {
// 矮个起开，反正也被挡着了。。。
s.pop();
}
// nums[i] 身后的 next great number
res[i] = s.empty() ? -1 : s.top();
s.push(nums[i]);
}
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> map = new HashMap<>();
int[] temp = new int[nums2.length];
int[] res = new int[nums1.length];
for (int i = 0; i < nums2.length; i++) {
map.put(nums2[i], i);
}
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int i = nums2.length-1; i >= 0; i--) {
while (!q.isEmpty() && nums2[i] >= q.peek()) {
q.pop();
}
temp[i] = q.isEmpty() ? -1 : q.peek();
q.push(nums2[i]);
}
for (int i = 0; i < nums1.length; i++) {
int index = map.get(nums1[i]);
res[i] = temp[index];
}
return res;
}
}
|
对于循环数组来说，可以用多种方式。
-
进行数组翻倍，这是一个常用套路。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n);
stack<int> s;
// 假装这个数组长度翻倍了
for (int i = 2 * n - 1; i >= 0; i--) {
// 索引要求模，其他的和模板一样
while (!s.empty() && s.top() <= nums[i % n])
s.pop();
res[i % n] = s.empty() ? -1 : s.top();
s.push(nums[i % n]);
}
return res;
}
|
-
首先找到最大值索引，从这里开始进行栈的构建。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
class Solution {
public int[] nextGreaterElements(int[] nums) {
if (nums == null || nums.length == 0)
return null;
int max = nums[0], index = 0;
for (int i = 1; i < nums.length; i++) {
if (max < nums[i]) {
max = nums[i];
index = i;
}
}
int[] res = new int[nums.length];
res[index] = -1;
ArrayDeque<Integer> q = new ArrayDeque<>();
q.push(max);
int i = index - 1;
while (i != index) {
if (i == -1)
i = nums.length - 1;
if (i == index) break;
while (!q.isEmpty() && nums[i] >= q.peek())
q.pop();
res[i] = q.isEmpty() ? -1 : q.peek();
q.push(nums[i]);
i--;
}
return res;
}
}
|
二、单调队列
与单调栈一样，就是一个队列结构，只不过维护成使得队列中的元素都是单调的。
单调栈主要解决 Next Great Number一类的算法问题，而单调队列可以解决滑动窗口问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length < k)
return null;
ArrayDeque<Integer> q = new ArrayDeque<>();
int[] res = new int[nums.length + 1 - k];
for (int i = 0; i < k; i++) {
while (!q.isEmpty() && nums[i] > q.getLast())
q.pollLast();
q.addLast(nums[i]);
}
res[0] = q.getFirst();
for (int i = 1; i <= nums.length - k; i++) {
int left = nums[i-1], right = nums[i+k-1];
if (left == q.getFirst())
q.pollFirst();
while (!q.isEmpty() && right > q.getLast())
q.pollLast();
q.addLast(right);
res[i] = q.getFirst();
}
return res;
}
}
|
关于单调队列的数据结构如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
/* 单调队列的实现 */
class MonotonicQueue {
LinkedList<Integer> q = new LinkedList<>();
public void push(int n) {
// 将小于 n 的元素全部删除
while (!q.isEmpty() && q.getLast() < n) {
q.pollLast();
}
// 然后将 n 加入尾部
q.addLast(n);
}
public int max() {
return q.getFirst();
}
public void pop(int n) {
if (n == q.getFirst()) {
q.pollFirst();
}
}
}
/* 解题函数的实现 */
int[] maxSlidingWindow(int[] nums, int k) {
MonotonicQueue window = new MonotonicQueue();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i < k - 1) {
//先填满窗口的前 k - 1
window.push(nums[i]);
} else {
// 窗口向前滑动，加入新数字
window.push(nums[i]);
// 记录当前窗口的最大值
res.add(window.max());
// 移出旧数字
window.pop(nums[i - k + 1]);
}
}
// 需要转成 int[] 数组再返回
int[] arr = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
arr[i] = res.get(i);
}
return arr;
}
|