- 单调栈是什么?
- 一、单调栈的实现
- 相关题目
- 1.子数组累加和乘以子数组最小值中的最大值
- 2.柱状图中最大的矩形
- [3.剑指 Offer II 040. 矩阵中最大的矩形](https://blog.csdn.net/xiaolu567/article/details/125211891)
- [4.统计全 1 子矩形](https://blog.csdn.net/xiaolu567/article/details/125212087)
- 5.子数组的最小值之和
单调栈是什么?
一种特别设计的栈结构,为了解决如下的问题:
给定一个可能含有重复值的数组arr,i位置的数一定存在如下两个信息
1)arr[i]的左侧离i最近并且小于(或者大于)arr[i]的数在哪?
2)arr[i]的右侧离i最近并且小于(或者大于)arr[i]的数在哪?
如果想得到arr中所有位置的两个信息,怎么能让得到信息的过程尽量快。
无重复数
如果加入的元素小于栈顶元素,则弹出栈顶元素,右侧最近小于元素为加入元素,左侧最近小于元素为栈顶元素的底下元素
最后单独结算栈,直到栈为空
public static int[][] getNearLessNoRepeat(int[] arr) {
int[][] res = new int[arr.length][2];
// 只存位置!
Stack stack = new Stack<>();
for (int i = 0; i < arr.length; i++) { // 当遍历到i位置的数,arr[i]
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
int j = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[j][0] = leftLessIndex;
res[j][1] = i;
}
stack.push(i);
}
while (!stack.isEmpty()) {
int j = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[j][0] = leftLessIndex;
res[j][1] = -1;
}
return res;
}
有重复数
用链表记录重复出现的元素,如果要弹出,统一结算链表里面的所有位置
public static int[][] getNearLess(int[] arr) {
int[][] res = new int[arr.length][2];
Stack> stack = new Stack<>();
for (int i = 0; i < arr.length; i++) { // i -> arr[i] 进栈
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
List popIs = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer popi : popIs) {
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 list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
while (!stack.isEmpty()) {
List popIs = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer popi : popIs) {
res[popi][0] = leftLessIndex;
res[popi][1] = -1;
}
}
return res;
}
相关题目
1.子数组累加和乘以子数组最小值中的最大值
2.柱状图中最大的矩形
3.剑指 Offer II 040. 矩阵中最大的矩形
4.统计全 1 子矩形
5.子数组的最小值之和


