写在前面:LeetCode刷题笔记
近来刷题,遇到单调栈,感觉这是个宝藏解题思想,在此记录一下!
单调栈定义
单调栈是指:站内元素保持一定单调性(单调递增或单调递减)的栈。这里的单调递增或递减是指从栈顶到栈底单调递增或递减。
主要解决的问题
- 比当前元素更大的下一个元素
- 比当前元素更大的前一个元素
- 比当前元素更小的下一个元素
- 比当前元素更小的前一个元素
单调栈解题模板代码
1 | stack<int> st; |
举栗子
寻找T = [73, 74, 75, 71, 69, 72, 76, 73]
数组每个元素右边第一个比自己大的元素位置,如果找不到,则用-1表示。
那么对应的结果应该为 [1, 2, 6, 5, 5, -1, -1]
分析:
73右边第一个比自己大的元素是74,数组下标位置为1
74右边第一个比自己大的元素是75,数组下标位置为2
75右边第一个比自己大的元素是76,数组下标位置为6
依次往下求解……
现在可以构造一个单调递增的栈来解决这个问题,以上述数组为例:[73, 74, 75, 71, 69, 72, 76, 73]
。从左到右遍历,如果栈为空或入栈元素值小于栈顶元素值,则入栈;反之,如果栈不为空或入栈元素大于栈顶元素值,则需要把比入栈元素小的元素全部出栈,同时对其进行相关操作。单调递减的栈反之。
以下是上述问题的代码:
1 | /*单调栈*/ |
LeetCode相关题目
参考文章: