当前位置：首页 > 算法 > 正文内容

【算法】单调栈

亿万年的星光1个月前 (03-07)算法303

一、单调栈

单调栈（Monotonic Stack）是一种特殊的栈结构，其核心思想是维护栈内元素的单调性（单调递增或单调递减）。单调栈通常用于解决与元素大小关系相关的问题，例如：

找到数组中每个元素的下一个更大（或更小）元素。
计算数组中每个元素左边或右边的第一个更大（或更小）元素。
解决与区间最值相关的问题（如最大矩形面积）。

二、特点

单调性：栈内元素始终保持单调递增或单调递减。
操作规则：
如果新元素满足单调性，直接压入栈。

如果新元素破坏了单调性，则弹出栈顶元素，直到满足单调性为止。

时间复杂度：由于每个元素最多入栈和出栈一次，因此时间复杂度通常为O(n)

三、应用场景

下一个更大元素：
给定一个数组，找到每个元素的下一个更大元素。
每日温度：
给定一个温度数组，计算每天需要等待多少天才能遇到更高的温度。
最大矩形面积：
给定一个柱状图，计算其中最大的矩形面积。
滑动窗口最大值：
在滑动窗口中快速找到最大值。

四、步骤

以找到数组中每个元素的下一个更大元素为例：

初始化：创建一个空栈和一个结果数组。
遍历数组：

如果当前元素大于栈顶元素，则栈顶元素的下一个更大元素就是当前元素。
弹出栈顶元素，并更新结果数组。
重复上述过程，直到当前元素小于等于栈顶元素或栈为空。
将当前元素压入栈。

处理剩余元素：遍历结束后，栈中剩余的元素没有下一个更大元素，将其结果设置为 -1。

【例题1】下一个更大元素

【题目描述】给定两个数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。对于 nums1 中的每个元素，找到其在 nums2 中对应位置的下一个更大元素。如果不存在，则输出 -1。

【样例输入】

【样例输出】

-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;
}

说明：