【算法】单调栈
一、单调栈
单调栈（Monotonic Stack）是一种特殊的栈结构，其核心思想是维护栈内元素的单调性（单调递增或单调递减）。单调栈通常用于解决与元素大小关系相关的问题，例如：
找到数组中每个元素的下一个更大（或更小）元素。
计算数组中每个元素左边或右边的第一个更大（或更小）元素。
解决与区间最值相关的问题（如最大矩形面积）。
二、特点
单调性：栈内元素始终保持单调递增或单调递减。
操作规则：
如果新元素满足单调性，直接压入栈。
时间复杂度：由于每个元素最多入栈和出栈一次，因此时间复杂度通常为O(n)
如果新元素破坏了单调性，则弹出栈顶元素，直到满足单调性为止。
三、应用场景
下一个更大元素：
给定一个数组，找到每个元素的下一个更大元素。每日温度：
给定一个温度数组，计算每天需要等待多少天才能遇到更高的温度。最大矩形面积：
给定一个柱状图，计算其中最大的矩形面积。滑动窗口最大值：
在滑动窗口中快速找到最大值。
四、步骤
以找到数组中每个元素的下一个更大元素为例：
初始化：创建一个空栈和一个结果数组。
遍历数组：
如果当前元素大于栈顶元素，则栈顶元素的下一个更大元素就是当前元素。
弹出栈顶元素，并更新结果数组。
重复上述过程，直到当前元素小于等于栈顶元素或栈为空。
将当前元素压入栈。
处理剩余元素：遍历结束后，栈中剩余的元素没有下一个更大元素，将其结果设置为
-1。
【例题1】下一个更大元素
【题目描述】给定两个数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。对于 nums1 中的每个元素，找到其在 nums2 中对应位置的下一个更大元素。如果不存在，则输出 -1。
【样例输入】
3 4 1 2 4 1 3 4 2
【样例输出】
-1 3 -1
【解释】
对于
4，在nums2中没有比它更大的元素，输出-1。对于
1，在nums2中下一个更大元素是3。对于
2，在nums2中没有比它更大的元素，输出-1
#include <iostream> #include <vector> #include <stack> using namespace std; vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { int n1 = nums1.size(); int n2 = nums2.size(); // 单调栈，用于找到 nums2 中每个元素的下一个更大元素 stack<int> st; vector<int> nextGreater(n2, -1); // 存储 nums2 中每个元素的下一个更大元素 // 遍历 nums2，找到每个元素的下一个更大元素 for (int i = 0; i < n2; i++) { while (!st.empty() && nums2[i] > nums2[st.top()]) { // 当前元素是栈顶元素的下一个更大元素 nextGreater[st.top()] = nums2[i]; st.pop(); } st.push(i); // 将当前元素的下标压入栈 } // 结果数组，用于存储 nums1 中每个元素的下一个更大元素 vector<int> result(n1, -1); // 遍历 nums1，根据 nums2 的结果找到对应值 for (int i = 0; i < n1; i++) { // 找到 nums1[i] 在 nums2 中的位置 for (int j = 0; j < n2; j++) { if (nums1[i] == nums2[j]) { result[i] = nextGreater[j]; // 获取对应的下一个更大元素 break; } } } return result; } int main() { vector<int> nums1 = {4, 1, 2}; vector<int> nums2 = {1, 3, 4, 2}; vector<int> result = nextGreaterElement(nums1, nums2); for (int num : result) { cout << num << " "; } cout << endl; return 0; }说明：
单调栈：我们使用单调栈来找到
nums2中每个元素的下一个更大元素。结果存储：将
nums2中每个元素的下一个更大元素存储在一个哈希表（或数组）中。遍历
nums1：根据nums1中的元素，从哈希表（或数组）中查找对应的下一个更大元素。
【例题2】每日温度
【题目描述】给定一个温度数组 temperatures，表示每天的温度。对于每一天，你需要等待多少天才能等到一个更高的温度。如果不存在这样的天，则输出 0。
【样例输入】
73 74 75 71 69 72 76 73
【样例输出】
1 1 4 2 1 1 0 0
【样例解释】
对于
73，第二天温度更高，等待1天。对于
74，第二天温度更高，等待1天。对于
75，第四天温度更高，等待4天。其他依此类推。
#include <iostream> #include <vector> #include <stack> using namespace std; vector<int> dailyTemperatures(vector<int>& temperatures) { int n = temperatures.size(); vector<int> answer(n, 0); // 初始化结果数组，默认值为 0 stack<int> st; // 单调栈，存储温度的下标 // 遍历温度数组 for (int i = 0; i < n; i++) { // 如果当前温度比栈顶温度高，则更新栈顶温度对应的等待天数 while (!st.empty() && temperatures[i] > temperatures[st.top()]) { int prevIndex = st.top(); // 栈顶温度的下标 st.pop(); answer[prevIndex] = i - prevIndex; // 计算等待天数 } st.push(i); // 将当前温度的下标压入栈 } return answer; } int main() { vector<int> temperatures = {73, 74, 75, 71, 69, 72, 76, 73}; vector<int> result = dailyTemperatures(temperatures); cout << "Daily Temperatures:" << endl; for (int num : result) { cout << num << " "; } cout << endl; return 0; }说明：
单调栈：我们使用单调栈来找到每个温度的下一个更高温度。
结果存储：将每个温度对应的等待天数存储在一个结果数组中。
过程说明：
第 0 天的温度是 73，第 1 天的温度是 74，因此等待天数为 1。
第 1 天的温度是 74，第 2 天的温度是 75，因此等待天数为 1。
第 2 天的温度是 75，第 6 天的温度是 76，因此等待天数为 4。
第 3 天的温度是 71，第 5 天的温度是 72，因此等待天数为 2。
第 4 天的温度是 69，第 5 天的温度是 72，因此等待天数为 1。
第 5 天的温度是 72，第 6 天的温度是 76，因此等待天数为 1。
第 6 天的温度是 76，未来没有更高的温度，因此等待天数为 0。
第 7 天的温度是 73，未来没有更高的温度，因此等待天数为 0。
例题3：柱状图中的最大矩形
【题目描述】给定一个非负整数数组 heights，表示柱状图中每个柱子的高度。找到柱状图中最大的矩形面积。
【样例输入】
2 1 5 6 2 3
【样例输出】
10
【解释】
最大的矩形是高度为 5 和 6 的柱子组成的区域，面积为 2 * 5 = 10。