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]的)就出栈,直到符合条件就找到了答案。

p8
class Solution {
public int[] dailyTemperatures(int[] tem) {
/*
写法1:Next Greater元素在栈中的写法
我们要找nums[i]右边首个比自身严格大的温度,因此要从右边起遍历温度
并且维护一个严格单调递增的栈(从左往右看)
单调找的操作有如下两种选择:
1.tem[i]<tem[栈顶] 说明找到tem[i]右边首个比自身大的温度,直接记录,最后tem[i]也要入栈
2.tem[i]>=tem[栈顶] 说明栈顶不是符合要求的元素,逐个弹出直至tem[i]<tem[栈顶],记录结果,最后tem[i]也要入栈
特殊情况:栈为空直接入栈
*/
int n = tem.length;
int[] res = new int[n];
// 单调栈存储索引即可
Deque<Integer> stack = new LinkedList<>();
for (int i = n - 1; i >= 0; i--) {
// tem[i]>=tem[栈顶] 弹出栈顶元素直至tem[i]<tem[栈顶]
while (!stack.isEmpty() && tem[i] >= tem[stack.peekFirst()]) stack.pollFirst();
// 记录结果:栈为空说明tem[i]后面没有比tem[i]温度高的,记录0;否则记录天数差值
res[i] = stack.isEmpty() ? 0 : stack.peekFirst() - i;
// tem[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) {
/*
写法2:基准元素nums[i]在栈中的写法
我们要找nums[i]右边首个比自身严格大的温度,因此要从左起遍历温度以便于基准元素入栈
维护一个单调递减栈(从左往右看) 一旦栈顶小可爱遇到比自己大的就冲出来并记录
1.tem[i]<=tem[栈顶] 说明栈顶的小可爱都还没找到下一个比自己严格大的元素,tem[i]直接入栈当下一个小可爱
2.tem[i]>tem[栈顶] 说明栈顶那群小可爱已经找到下一个比自己严格大的元素,出栈并记录,最后别忘了tem[i]也要入栈找自己的下一个比自身大的元素
特殊情况:栈为空直接入栈即可,栈顶没有人要找下一个更大的元素
*/
int n = tem.length;
int[] res = new int[n];
// 单调栈存储索引即可
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < n; i++) {
// 当栈顶小可爱遇到比自己大的tem[i],c出栈并记录后tem[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的选用习惯:

目前比较推荐以下两种:

/*
写法1
*/
Deque<Integer> st = new LinkedList<>();
st.push(i); // 元素入栈
st.peek(); // 查看栈顶元素
st.pop(); // 弹出栈顶元素

/*
写法2
*/
Deque<Integer> st = new LinkedList<>();
st.addFirst(i); // 元素入栈
st.peekFirst(); // 查看栈顶元素
st.pollFirst(); // 弹出栈顶元素

4.单调栈与范围管辖问题(Hard)

2104. 子数组范围和

int[] nums;
int n;

public long subArrayRanges(int[] _nums) {
/*
方法2:单调栈
我们要找nums[i]中所有的子数组的max-min的和,那么我们罗列出所有子数组,其最大值和最小值必定出自于nums[i]其中某一个
换一个角度,我们假设nums[i]作为max管辖的子数组个数为k1,最为min管辖的子数组个数为k2,那么nums[i]*(k2-k1)就是nums[i]这个数字贡献的范围和
我们怎样知道某个nums[i]的管辖范围?很显然要找到nums[i]在包含自身的哪个范围内是“老大”
例如作为max就要知道自己左右两边首个比自己大的数字,在这两个数字之间nums[i]就是老大
这种情况显然就要用到单调找来查找自己的管辖范围
以求最大值为例进行说明,我们要求自己左右两边比自己大的数字,先以左边为例进行说明
在栈中从左到右维护一个单调递减栈,一旦遇到nums[i]<nums[栈顶]就说明nums[i]找到了比自己大的数字位置
找到nums[i]左右两边比自己大的数字位置之后,例如 nums = [4,-2,-3,4,1] 计算得idx=3的元素范围为[-1,5]
这里是下一个比自己大的数字范围,因此包含idx=3的子数组个数为:(3-(-1))*(5-3)=8 左边4个:3 2,3 1,2,3 0,1,2,3
右边2个:∅ 4 换算到一般情况就是 (idx-left)*(right-idx)
注意点:nums = [4,-2,-3,4,1] 这种情况下我们会求得第一个4的范围为:[0,4] 同理第二个范围也为:[0,4]
这两种情况会重复计算第一个4与第二个4共存的情况
因此我们在单调栈计算的时候,约定左边找比自己严格大(小)的首个数字,右边找大于等于(小于等于)自己的首个数字
时间复杂度:O(N) 空间复杂度:O(N)
*/
nums = _nums;
n = nums.length;
long res = 0;
// max[i]表示nums[i]作为最大值的子数组个数,min[i]表示nums[i]作为最小值的子数组个数
int[] max = getCnt(true), min = getCnt(false);
// 计算所有子数组范围和
for (int i = 0; i < n; i++) {
res += (long) (max[i] - min[i]) * nums[i];
}
return res;
}

// getCnt(true)表示获取nums[i]最大值的子数组个数,反之就是获取nums[i]最大值的子数组个数
private int[] getCnt(boolean isMax) {
// ans[i]表示要返回的数据
int[] ans = new int[n];
// left[i]表示nums[i]左边首个严格大于(小于)自身的数字索引
// right[i]表示nums[i]左边首个非严格大于(小于)自身的数字索引
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) {
/*
单调栈的应用:
不妨枚举nums[i]并假设某包含nums[i]的子段是长度为k的某段中最小的数字
在该段中其余数字都大于nums[i],只要nums[i]>threshold/k,那么段内的所有元素均大于threshold/k
我们只需要求出有没有这样的nums[i]就可以知道是否有符合题意的k
怎样维护某个nums[i]在某个段内是最小的数字?我们只需要找到nums[i]左边和右边首个严格小于nums[i]的索引
那么索引之间就是nums[i]这段的波及范围
快速求nums[i]左边和右边首个小于nums[i]的元素属于Next Greater问题,可以用单调栈解决
时间复杂度:O(N) 空间复杂度:O(N)
*/
int n = nums.length;
// 两个单调栈st1与st2
Deque<Integer> st1 = new LinkedList<>(), st2 = new LinkedList<>();
// left[i]存储nums[i]左边首个严格小于nums[i]的数字索引,不存在时为-1
// right[i]存储nums[i]右边首个严格小于nums[i]的数字索引,不存在时为n
int[] left = new int[n], right = new int[n];
// 正序遍历求left[i]
for (int i = 0; i < n; i++) {
// 遇到nums[i]<=nums[栈顶索引] -> 弹出栈顶索引直至nums[i]>nums[栈顶索引]
// 此时nums[栈顶索引]就是nums[i]左边首个严格小于nums[i]的数字
// 被弹出的那些栈顶元素是不可能成为后面left[i]有效取值的,因为会优先取到当前的nums[i]
// e.g. nums[st1]=[1,2,4,5] nums[i]=3 显然4与5不符合题意弹出 3才是符合题意的 加入后面有个6进来了
// 必然会优先取到3而不会取更前面的4与5
while (!st1.isEmpty() && nums[st1.peek()] >= nums[i]) st1.pop(); // 一直弹出直至st1严格递增
left[i] = st1.isEmpty() ? -1 : st1.peek(); // 栈顶的必定1严格小于nums[i]并且是最近的(-1表示取全部)
st1.push(i); // 每次都要入栈
}
// 倒序遍历求right[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);
}
// 枚举nums[i]根据其波及范围确定到k,再判断k是否合法
for (int i = 0; i < n; i++) {
int k = right[i] - left[i] - 1; // 实际范围:[left[i]+1,right[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;
// max[i]表示nums[i]作为最大值的子数组个数,min[i]表示nums[i]作为最小值的子数组个数
int[] max = getCnt(true), min = getCnt(false);
// 计算所有子数组范围和
for (int i = 0; i < n; i++) {
res += (long) (max[i] - min[i]) * nums[i];
}
return res;
}

// getCnt(true)表示获取nums[i]最大值的子数组个数,反之就是获取nums[i]最大值的子数组个数
private int[] getCnt(boolean isMax) {
// ans[i]表示要返回的数据
int[] ans = new int[n];
// left[i]表示nums[i]左边首个严格大于(小于)自身的数字索引
// right[i]表示nums[i]左边首个非严格大于(小于)自身的数字索引
int[] left = new int[n], right = new int[n];
// 利用单调栈查找管辖范围(数组模拟栈结构,在范围小得时候非常好用)
int[] stack = new int[n + 1];
int ptr = 0; // ptr指代当前栈中栈顶元素所在stack数组的位置
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.记录的一些练习题

6.1 LC402. 移掉 K 位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ,移除这个数中的 k 位数字,使得剩下的数字最小。

请你以字符串形式返回这个最小的数字。

p24

思路:

单调栈:维护一个栈底->栈顶单调递增的栈(参考"笨猪爆破组"题解)

要尽量让高位维护一个递增的趋势,即去除高位的降序对

如: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<>();
// 遍历num每一个数字
for (char ch : num.toCharArray()) {
// 找出降序对
while (k > 0 && !stack.isEmpty() && stack.peekFirst() > ch) {
// 这里弹出一个表明num中删除了一个(降序对的前一个元素)
stack.pollFirst();
k--;
}
// 为了去除前导0:非0的直接加入;当前栈有垫底的,啥都可以加入
if(ch != '0' || !stack.isEmpty()) stack.addFirst(ch);
}
// 遍历完num所有数字,但是k还大于0,要截取前面的数字(相当于把栈顶部分弹出k个)
while (k-- > 0 && !stack.isEmpty()) stack.pollFirst();
while (!stack.isEmpty()) sb.append(stack.pollFirst());
// 这里要考虑到栈为空的情况,sb没东西表明为0
return sb.length() == 0 ? "0" : sb.reverse().toString();
}
}

6.2 LC316. 去除重复字母

给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。

需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

p25

思路:

单调栈+标记:

参考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<>();
// 遍历字符串s
for (char c : s.toCharArray()) {
// 字符c次数-1
count[c - 'a']--;
// 栈中已经有了,不再加入
if(inStack[c - 'a']) continue;
// 字符c入栈,入栈前要将所有的字典序比c大且后面还会出现的字母弹出
while (!stack.isEmpty() && c < stack.peekFirst()) {
// 栈顶字母后面没有出现了,不能再弹出
if(count[stack.peekFirst() - 'a'] == 0) break;
// 否则可以弹出
char poll = stack.pollFirst();
// 弹出的就将栈中的记录删除
inStack[poll - 'a'] = false;
}
// 字符c入栈
stack.addFirst(c);
// 入栈后要标记
inStack[c - 'a'] = true;
}
// 最后将栈中的元素逐个弹出存入sb中
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() 获取堆栈中的最小元素。

p26

思路:

单调递增栈(栈顶->栈底)维护栈中元素最小值:

方法1:完全同步栈:一个为常规栈(主栈);另一个为同步栈,保存每一步中主栈元素最小值

这个方法要求主栈与同步栈的元素个数严格相等,加入时两个同步加入,弹出时两个同步弹出,无需多加判断

这种方法存在一定的冗余存储,于是就有了方法2

方法2:主栈+单调栈:一个为主栈,另一个为单调递增栈(栈顶->栈底),当且仅当要加入的元素x<=单调栈栈顶时才加入

其余情况不加入;同理,弹出时要看单调栈栈顶是否与主栈弹出的元素相等,若相等的话就弹出。

注意:这个单调栈是非主动挤压型的,也就是在加入元素时,如果当前元素不能与现在的单调栈构成单调递增栈会主动放弃,而不会将栈中不符合条件的全部弹出(这显然会损失掉部分最小值信息!)

class MinStack_1 {
Deque<Integer> stack;
Deque<Integer> minStack;
// 构造器
public MinStack_1() {
stack = new LinkedList<>();
minStack = new LinkedList<>();
// 这一步很关键:就是让首个加入的x也可以顺利加入minStack
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();
// 这里无论pop是何止都要弹出minStack栈顶,因为两个栈的个数总是一致的
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<>();
// 这一步很关键:就是让首个加入的x也可以顺利加入minStack
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();
// 区别就在这里:这里要看与pop相等的栈顶才弹出
if(minStack.peekFirst() == pop) minStack.pollFirst();
}

// 获取栈顶元素(不弹出)
public int top() {
return stack.peekFirst();
}

// 获取栈中最小值
public int getMin() {
return minStack.peekFirst();
}
}

这道题要时刻注意判空异常,还有初始化辅助栈要将不影响首个元素入栈的Integer.MAX_VALUE加入!!!记住了