上篇文章我们讨论了单调栈的相关知识，并给出了 不含相同值的单调栈 如何实现的代码。（还没看过上篇文章的赶快 点我 查看哦！）
本文我们继续深入学习，思考 含有相同值的单调栈 如何实现。
由已知推未知：没有相同值的单调栈中我们存放的是各元素的下标。因此，当含有相同值时，它们的 下标是不一样的 ，我们用链表将 相同值 的元素 下标链接起来。
此时单调栈中存放的就是一个一个的 链表 了。
实现思路
上次我们寻找的是两侧最近且大于某个数的，这次我们换成 寻找最近且小于某个数 的（其实本质都一样，换个“>”、"<"号即可）。（栈底小 -> 栈顶大）：
新元素的处理： 当一个新元素到来时，先与栈顶元素进行比较。
- 若比栈顶元素大：创建一个新的链表后直接压栈保存；
- 若比栈顶元素小：需要弹出栈顶链表中所有元素，直到栈空或比栈顶元素大后压栈。
- 若遇到相同大小时：加入到链表尾部。
弹出时更新信息： 当弹出栈顶元素时，此时次栈顶元素和新来元素就是所求的左右两侧距离最近的且小于该元素的值，更新该链表中所有元素信息 。
没看懂！没关系，看图例：
注意： 栈中存放的是元素的下标。
代码
public static int[][] getNearLess(int[] arr) {
int n = arr.length;
int[][] res = new int[n][2];
// 链表栈
Stack<List<Integer>> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
List<Integer> popls = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer popi : popls) {
res[popi][0] = leftLessIndex;
res[popi][1] = i;
}
}
// 相等时加入
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
stack.peek().add(Integer.valueOf(i));
} else {
// 小于时，新增一个链表，加入栈顶
ArrayList<Integer> list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
while (!stack.isEmpty()) {
List<Integer> popls = stack.pop();
// 从链表尾部依次弹出
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer popi : popls) {
res[popi][0] = leftLessIndex;
res[popi][1] = -1;
}
}
return res;
}
代码解释
和上篇文章代码非常类似，只是这次栈中存放的是 下标链表，需要注意以下几点：
- 新到元素与栈顶元素相等时，加入到栈顶链表的 链表尾部；
- 新到元素大于栈顶元素时，生成一个新的链表 后再入栈（此时只有一个元素的链表）；
- 新到元素小于栈顶元素时，栈顶链表全部出栈，并记录信息。
- 当无新元素到来时，也需要出栈。栈顶链表 出栈的顺序 为 从链表尾部依次弹出 ！！！
总结
这两篇文章的学习，我们了解了对于 无重复值 和 有重复值 两种不同类型的单调栈的处理方式。
通过一步一步的图例，相信小伙伴们已经掌握了这两种最基本的单调栈思路和代码。
可能有的小伙伴有疑问了，无重复值不是可以看做特殊的有重复值么，那所有的都用有重复值的代码不就行了么？接下来我们将通过一些单调栈的题目体会这两种不同类型的区别。
~ 点赞 ~ 关注 ~ 评论 ~ 不迷路 ~！！！
关注回复「ACM紫书」获取 ACM 算法书籍~
点赞👍评论👀分享🤩
