单调栈入门
简介
受启发与ikaruga)的题解，自己复习单调栈。
单调栈分为单调递增栈和单调递减栈：
- 单调递增栈即栈内元素保持单调递增的栈
- 单调递减栈即栈内元素保持单调递减的栈
操作规则（以单调递增栈为例）：
- 如果新的元素比栈顶元素大，就入栈
- 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小
加入这样一个规则之后，会有什么效果：
- 栈内的元素是递增的
- 当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素
举个例子，配合下图，现在索引在6，栈内元素分别是1，5，6
接下来新元素是2，那么6需要出栈。
当6出栈时，右边2代表是6右边第一个比6小的元素。
- 当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素
当6出栈时，5成为新的栈顶，那么5代表是6左边第一个比6小的元素。
Java模版：
int[] arr = {
2, 1, 5, 6, 2, 3};
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < arr.length; i++) {
while (!stack.isEmpty() && stack.peek() > arr[i]) {
stack.pop();
}
stack.push(arr[i]);
}
查看14道真题和解析
字节跳动公司氛围 642人发布