1.单调栈可以解决的问题：
我们常常遇到要在O(N)的时间复杂度内求出当前对象 nums[i] 左边或者右边首个比自己大或者小的情况
这种问题通常称为Next Greater问题
就相当于你是一个人，往两边看首先被哪个高个子挡住，这个高个子满足两个条件：
1.身高比你高；2.在某一方向中比你高的人中距离你最近
这种条件可能比较明显，739. 每日温度 496. 下一个更大元素 I 这类型要你直接求下一个更大更小的元素是什么
也有可能是比较隐秘的，抽象成波及范围的，这属于单调栈中的困难题了 42. 接雨水 6119. 元素值大于变化阈值的子数组
求某个元素的影响范围，通常都是找到两边首个比自己小的或大的 left 与 right，然后这个[left,right]通常就是影响区间的
例如[left,right]可以接住高度为max-nums[i]的雨水，可以组成某某区间等…
2.单调栈的两种写法：
以739. 每日温度 为例进行说明，一般来说有两种写法：
1.Next Greater元素在栈中的写法（25ms/51.1MB）
举个🌰：现在要寻找的nums[i]左边首个严格小于nums[i]的元素，st = [1, 2, 3, 6]
若nums[i]=7，直接取栈顶的6作为左边首个严格小于nums[i]的元素
若nums[i]=3，要将栈顶中>=nums[i]的元素全部弹出，直至栈顶严格小于nums[i] 此时st = [1, 2]，那么2就是所求
要点： 如果找nums[i] 右边的元素，那么从右边遍历起以便于 Next Greater元素先入栈；
反之，如果找nums[i] 左边的元素，那么从左边遍历起以便于 Next Greater元素先入栈；
当前遍历到的nums[i]就是基准元素，如果找右边首个大于nums[i]的就要一直保持nums[i]是最左边的且是最小的，不符合条件的栈顶元素（<=nums[i]的）就出栈，直到符合条件就找到了答案。
class Solution {
public int[] dailyTemperatures(int[] tem) {
int n = tem.length;
int[] res = new int[n];
Deque<Integer> stack = new LinkedList<>();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && tem[i] >= tem[stack.peekFirst()]) stack.pollFirst();
res[i] = stack.isEmpty() ? 0 : stack.peekFirst() - i;
stack.addFirst(i);
}
return res;
}
}
|
2.基准元素nums[i] 在栈中的写法(23ms/56.8MB)
举个🌰：现在要寻找的nums[i]右边首个严格大于nums[i]的元素，st = [8, 6, 4, 3]
现在我们栈中的元素还要找自己右边首个大于自己的元素呢，嗷嗷待哺~~~
若nums[i]=2，比栈顶还小，直接入栈得了，所有人都还没找到比自己小的元素~~~此时 st = [8, 6, 4, 3, 2]
此时来了nums[i]=4，栈上方的2与3显然是找到了右边首个比自己严格大的元素，出栈并记录
但是栈中的4还是没有找到比自己严格大的，因此只能期待接下来有没有更大的数字了~~~
此时st = [8, 6, 4, 4] 若此时再来个5那么这两个可怜的4就有机会出栈并记录了~~~
要点： 如果找nums[i] 右边的元素，那么从左边遍历起以便于基准元素nuns[i]先入栈；
反之，如果找nums[i] 左边的元素，那么从右遍历起以便于基准元素nums[i]先入栈；
当前遍历到的nums[i]就是基准元素，且一直要保持栈顶是最小的，一旦新来的nums[i]严格大于栈顶的小可怜，就代表栈顶的小可怜可以出栈记录了
代码如下：
public int[] dailyTemperatures(int[] tem) {
int n = tem.length;
int[] res = new int[n];
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && tem[i] > tem[stack.peekFirst()]) {
int poll = stack.pollFirst();
res[poll] = i - poll;
}
stack.addFirst(i);
}
return res;
}
|
由运行结果可知两种写法时间消耗与空间消耗接近，个人比较推荐写法1
3.API的选用习惯：
目前比较推荐以下两种：
Deque<Integer> st = new LinkedList<>();
st.push(i);
st.peek();
st.pop();
Deque<Integer> st = new LinkedList<>();
st.addFirst(i);
st.peekFirst();
st.pollFirst();
|
4.单调栈与范围管辖问题（Hard）
2104. 子数组范围和
int[] nums;
int n;
public long subArrayRanges(int[] _nums) {
nums = _nums;
n = nums.length;
long res = 0;
int[] max = getCnt(true), min = getCnt(false);
for (int i = 0; i < n; i++) {
res += (long) (max[i] - min[i]) * nums[i];
}
return res;
}
private int[] getCnt(boolean isMax) {
int[] ans = new int[n];
int[] left = new int[n], right = new int[n];
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && (isMax ? nums[i] >= nums[stack.peekFirst()] : nums[i] <= nums[stack.peekFirst()])) stack.pollFirst();
left[i] = stack.isEmpty() ? -1 : stack.peekFirst();
stack.addFirst(i);
}
stack.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && (isMax ? nums[i] > nums[stack.peekFirst()] : nums[i] < nums[stack.peekFirst()])) stack.pollFirst();
right[i] = stack.isEmpty() ? n : stack.peekFirst();
stack.addFirst(i);
}
for (int i = 0; i < n; i++) {
ans[i] = (i - left[i]) * (right[i] - i);
}
return ans;
}
|
2334. 元素值大于变化阈值的子数组
class Solution {
public int validSubarraySize(int[] nums, int threshold) {
int n = nums.length;
Deque<Integer> st1 = new LinkedList<>(), st2 = new LinkedList<>();
int[] left = new int[n], right = new int[n];
for (int i = 0; i < n; i++) {
while (!st1.isEmpty() && nums[st1.peek()] >= nums[i]) st1.pop();
left[i] = st1.isEmpty() ? -1 : st1.peek();
st1.push(i);
}
for (int i = n - 1; i >= 0; i--) {
while (!st2.isEmpty() && nums[st2.peek()] >= nums[i]) st2.pop();
right[i] = st2.isEmpty() ? n : st2.peek();
st2.push(i);
}
for (int i = 0; i < n; i++) {
int k = right[i] - left[i] - 1;
if (nums[i] > threshold / k) return k;
}
return -1;
}
}
|
5.栈结构写法的优化
以2104. 子数组范围和为例进行说明
栈结构还可以优化成数组的写法，辅助一个ptr指针，在数据范围小的时候非常节省时间与空间
其中ptr指代当前栈中栈顶元素所在stack数组的位置
prt指针可以初始化为-1或者0表示栈底索引，栈的容量初始化为可能出现的最大栈中元素个数
入栈： stack[++ptr]=i 腾出空位再赋值
出栈： 直接ptr–即可，后面新元素入栈会覆盖掉旧的痕迹
查看栈顶元素： 返回stack[ptr]就是
清空栈： ptr=0（-1）
int[] nums;
int n;
public long subArrayRanges(int[] _nums) {
nums = _nums;
n = nums.length;
long res = 0;
int[] max = getCnt(true), min = getCnt(false);
for (int i = 0; i < n; i++) {
res += (long) (max[i] - min[i]) * nums[i];
}
return res;
}
private int[] getCnt(boolean isMax) {
int[] ans = new int[n];
int[] left = new int[n], right = new int[n];
int[] stack = new int[n + 1];
int ptr = 0;
for (int i = 0; i < n; i++) {
while (ptr > 0 && (isMax ? nums[i] >= nums[stack[ptr]] : nums[i] <= nums[stack[ptr]])) ptr--;
left[i] = ptr == 0 ? -1 : stack[ptr];
stack[++ptr] = i;
}
ptr = 0;
for (int i = n - 1; i >= 0; i--) {
while (ptr > 0 && (isMax ? nums[i] > nums[stack[ptr]] : nums[i] < nums[stack[ptr]])) ptr--;
right[i] = ptr == 0 ? n : stack[ptr];
stack[++ptr] = i;
}
for (int i = 0; i < n; i++) {
ans[i] = (i - left[i]) * (right[i] - i);
}
return ans;
}
|
6.记录的一些练习题
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。
请你以字符串形式返回这个最小的数字。
思路：
单调栈:维护一个栈底->栈顶单调递增的栈(参考"笨猪爆破组"题解)
要尽量让高位维护一个递增的趋势，即去除高位的降序对
如:1234532与5321234，当组成数字相同时，必定是前面高位递增数值会更加小
现在任务变成：删除k位使得高位的递增序列尽量长(删除高位尽可能多的递减对)
单调栈按顺序存储想要的数字，其中栈顶为栈中最大值，将当前遍历到的数字与栈顶比较决定栈顶的去留
设栈顶数字为B，当前遍历到的数字为A：
1.B > A：B与A之间组成递减对，此时去掉B，A代替B的位置可以使得数值变小
2.B <= A：B与A之间组成递增对，让A入栈是最好的选择
这里要注意几个问题：
1.能去除（出栈）的数字个数有限，不能超过k，因此超过k部分直接加入，不保证栈的单调性
2.考虑去除前导0的情况，前导0不能加入；换句话说就是：非0和有垫底的0可以加入
3.当前num中的降序对 < k时，删除完所有降序对后，num已经是递增，此时截取前面部分就是最小的;
4.当前num中的降序对 >= k时，恰好删除完或者有剩余，此时num后面的直接加入即可，不用考虑保持栈的单调性
class Solution {
public String removeKdigits(String num, int k) {
if (num.length() == k) return "0";
StringBuilder sb = new StringBuilder();
Deque<Character> stack = new LinkedList<>();
for (char ch : num.toCharArray()) {
while (k > 0 && !stack.isEmpty() && stack.peekFirst() > ch) {
stack.pollFirst();
k--;
}
if(ch != '0' || !stack.isEmpty()) stack.addFirst(ch);
}
while (k-- > 0 && !stack.isEmpty()) stack.pollFirst();
while (!stack.isEmpty()) sb.append(stack.pollFirst());
return sb.length() == 0 ? "0" : sb.reverse().toString();
}
}
|
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。
需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
思路：
单调栈+标记:
参考labuladong的题解，本题的关键点有几个：
1.要求最后的字母没有重复，且每个字母都要出现一次
2.要按照原来字母的出现顺序输出(相对顺序不变)
3.满足条件1与2前提下的要求返回字符串的字典序最小
其中，条件1可以用boolean数组或者HashSet等数据结构来进行存储，如果前面出现过就不加入；
条件2要求相对顺序不变，可以用一个指针进行遍历再存储，只要满足数据存储有序的数据结构即可
最关键的是条件3，要求字典序最小的情形输出。这里就是要用到单调栈最深层的原因
因为我们要操作"临近元素"(降序对)！为什么要操作降序对？
这个可以参考 402. 移掉 K 位数字(中等)
402题是要求删掉k个数字使得最后的结果最小，核心就是优先找出"降序对"，例如：76，98，54…
因为当你删除了降序对前面的数字后，后面数字的居上取代了原来前面的数字，必定使得数字变小
A=123a56与B=123b56，a与b当前面完全一致，整个数字大小取决于a与b的大小，a>b则A>B
回到本题中，我们要使得字典序在满足其他条件的前提下尽可能小，那么可以选择删掉降序对的前面字母
由于后来居上的特征，降序对是不断变化的，因此要用栈这种结构来模拟，每当当前字母ch满足其他条件时，
如果与栈顶组成降序对，说明我现在有机会让字典序变小，因此必然会想着将栈顶元素弹出！
可是本题要求所有字母都要出现一次，你把栈顶弹出了之后万一后面不再出现栈顶的字母不就不满足题意？
因此还要看看后面有没有再出现栈顶元素：
1.若没有出现则不能弹出，ch乖乖进去吧！
2.若后面还会出现，可以放心弹出，后面还可以加入该字母的，这样既使得字典序尽量小又能满足条件！
做法就是用count数组维护当前位置后面剩余的每个字母个数，当个数减为0时说明后面没有了！
class Solution {
public String removeDuplicateLetters(String s) {
StringBuilder sb = new StringBuilder();
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
boolean[] inStack = new boolean[26];
Deque<Character> stack = new LinkedList<>();
for (char c : s.toCharArray()) {
count[c - 'a']--;
if(inStack[c - 'a']) continue;
while (!stack.isEmpty() && c < stack.peekFirst()) {
if(count[stack.peekFirst() - 'a'] == 0) break;
char poll = stack.pollFirst();
inStack[poll - 'a'] = false;
}
stack.addFirst(c);
inStack[c - 'a'] = true;
}
while (!stack.isEmpty()) {
sb.append(stack.pollFirst());
}
return sb.reverse().toString();
}
}
|
面试题 03.02. 栈的最小值 同 155.最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
思路：
单调递增栈(栈顶->栈底)维护栈中元素最小值:
方法1：完全同步栈：一个为常规栈（主栈）；另一个为同步栈，保存每一步中主栈元素最小值
这个方法要求主栈与同步栈的元素个数严格相等，加入时两个同步加入，弹出时两个同步弹出，无需多加判断
这种方法存在一定的冗余存储，于是就有了方法2
方法2：主栈+单调栈：一个为主栈，另一个为单调递增栈(栈顶->栈底)，当且仅当要加入的元素x<=单调栈栈顶时才加入
其余情况不加入；同理，弹出时要看单调栈栈顶是否与主栈弹出的元素相等，若相等的话就弹出。
注意：这个单调栈是非主动挤压型的，也就是在加入元素时，如果当前元素不能与现在的单调栈构成单调递增栈会主动放弃，而不会将栈中不符合条件的全部弹出(这显然会损失掉部分最小值信息!)
class MinStack_1 {
Deque<Integer> stack;
Deque<Integer> minStack;
public MinStack_1() {
stack = new LinkedList<>();
minStack = new LinkedList<>();
minStack.addFirst(Integer.MAX_VALUE);
}
public void push(int x) {
stack.addFirst(x);
int min = Math.min(minStack.peekFirst(), x);
minStack.addFirst(min);
}
public void pop() {
int pop = stack.pollFirst();
minStack.pollFirst();
}
public int top() {
return stack.peekFirst();
}
public int getMin() {
return minStack.peekFirst();
}
}
----------------------------------------------------------------------------------------------------------------
class MinStack_2 {
Deque<Integer> stack;
Deque<Integer> minStack;
public MinStack_2() {
stack = new LinkedList<>();
minStack = new LinkedList<>();
minStack.addFirst(Integer.MAX_VALUE);
}
public void push(int x) {
stack.addFirst(x);
if(x <= minStack.peekFirst()) minStack.addFirst(x);
}
public void pop() {
int pop = stack.pollFirst();
if(minStack.peekFirst() == pop) minStack.pollFirst();
}
public int top() {
return stack.peekFirst();
}
public int getMin() {
return minStack.peekFirst();
}
}
|
这道题要时刻注意判空异常，还有初始化辅助栈要将不影响首个元素入栈的Integer.MAX_VALUE加入!!!记住了
