单调栈的定义以及使用模板

2024-05-04 23:59
10人已看

一、单调栈

1.1 什么是单调栈

单调栈（Monotonic Stack）是一种特殊的栈数据结构，主要用于解决一些与单调性相关的问题。

单调栈的特点是栈内元素保持单调性，通常是单调递增或单调递减。

注意：这里定义的顺序是从「栈顶」到「栈底」。有的文章里是反过来的。

本文全文以「栈顶」到「栈底」的顺序为基准来描述单调栈。

1.2 应用场景

单调栈可以在时间复杂度为 $O (n)$ 的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素。

这里指的是，数组里面的每个元素的左边或者右边第一个比他大的值，都可以通过一次遍历得到

所以单调栈一般用于解决以下几种问题：

寻找左侧第一个比当前元素大的元素。
寻找左侧第一个比当前元素小的元素。
寻找右侧第一个比当前元素大的元素。 496. 下一个更大元素 I - 力扣（LeetCode）
寻找右侧第一个比当前元素小的元素。

1.3 leetcode 练习题

2866. 美丽塔 II - 力扣（LeetCode）

下一个更大元素 I（单调栈模板题）
下一个更大元素 II
下一个更大元素 IV
132 模式
每日温度
股票价格跨度
链表中的下一个更大节点
表现良好的最长时间段
商品折扣后的最终价格
使数组按非递减顺序排列

在熟悉单调栈后，我们可以尝试利用单调栈解决更为复杂的问题：

42. 接雨水 - 力扣（LeetCode）

907. 子数组的最小值之和 - 力扣（LeetCode）

二、单调栈实现方案

2.1 求解方法

解法有点绕口，可以简单记为以下三条规则：

无论哪种题型，都建议从左到右遍历元素。
查找「比当前元素大的元素」就用单调递增栈，查找「比当前元素小的元素」就用单调递减栈。
从「左侧」查找就看「插入栈」时的栈顶元素，从「右侧」查找就看「弹出栈」时即将插入的元素。（栈底->栈顶->插入元素的顺序是从左到右的, 我们可以从这点来理解并记忆这条规则）

该规则的详细解释查看算法数据结构——关于单调栈（Monotone Stack）的详细讲解及应用案例-CSDN博客

2.2 代码模板

代码模板撰写顺序：

构造单调栈
添加从左侧或者右侧查看的代码

以 496. 下一个更大元素为基础，在实际编写代码的时候，我们首先构造单调栈：

// 单调递减栈 (只有比栈顶元素大的元素才能直接进栈)
for(int num : nums2){
	while(!stack.isEmpty() && num <= stack.peek()){
		stack.pop(); // 保证栈中保留的都是比 num 小的值
	}
	stack.push(num);
}

// 单调递增栈（只有比栈顶元素小的元素才能直接进栈）
for(int num : nums2){
	while(!stack.isEmpty() && num >= stack.peek()){
		stack.pop();
	}
	stack.push(num);
}

然后，再添加从左侧或者右侧查看的代码（ -1 表示没有找到最值）

// 单调递增栈， 左边查看
for(int num : nums2){
	while(!stack.isEmpty() && num <= stack.peek()){
		stack.pop();
	}
	map.put(num, stack.isEmpty() ? -1 : stack.peek());  // 左边查看
	stack.push(num);
}

// 单调递增栈， 左边查看
for(int num : nums2){
	while(!stack.isEmpty() && num <= stack.peek()){
	    map.put(stack.peek(), num);  // 右边查看
		stack.pop();
	}
	map.put(num, -1 );  // 保证没有找到最值的元素能够赋值为 -1
	stack.push(num);
}

注意：当左边查看时，入栈时， stack.peek() 是 num 的左边第一个最大值；右边查看时，出栈时，num 是 stack.peek() 的右边第一个最大值。栈底->栈顶->插入元素的顺序是从左到右的, 我们可以从这点来理解并记忆这条规则，从而理解 栈顶和插入元素的对应关系。

个人技术分享