C11第5章单调栈

admin

1. 单调栈的核心原理
单调栈通过维护栈内元素的单调性（递增或递减），实现了在 O (n) 时间内解决一系列问题。上述代码中使用了 STL 的stack容器，主要维护的是元素的索引而非值，这样既可以获取元素值，又能知道元素在数组中的位置。
2. 主要函数说明
nextGreaterElement 函数：
使用单调递减栈（栈顶元素值最小）
遍历数组时，对于每个元素，弹出栈中所有比它小的元素，当前元素就是这些弹出元素的 "下一个更大元素"
最后将当前元素入栈，保持栈的递减性
nextSmallerElement 函数：
使用单调递增栈（栈顶元素值最大）
逻辑与 nextGreaterElement 相反，寻找比当前元素小的下一个元素
largestRectangleArea 函数：
两次使用单调栈分别计算每个柱子的左右边界（左侧和右侧第一个更小的元素）
对于每个柱子，最大矩形面积 = 高度 × (右侧边界索引 - 左侧边界索引 - 1)
取所有柱子的最大面积作为结果
3. 示例输出说明
示例 1 中，数组[2, 1, 2, 4, 3]的下一个更大元素为[4, 2, 4, -1, -1]
2 的下一个更大元素是 4
1 的下一个更大元素是 2
2 的下一个更大元素是 4
4 和 3 没有更大元素，所以为 - 1
示例 2 中，数组[3, 4, 2, 7, 5]的下一个更小元素为[2, 2, -1, 5, -1]
示例 3 中，直方图[2, 1, 5, 6, 2, 3]的最大矩形面积为 10
由高度为 5 和 6 的柱子组成，宽度为 2，面积为 5×2=10
通过这些示例可以看出，单调栈在解决与元素前后大小关系相关的问题时非常高效，能够将时间复杂度从 O (n²) 降至 O (n)。

[C++] 纯文本查看 复制代码

#include <iostream>
#include <vector>
#include <stack>  // STL栈容器

using namespace std;

/**
 * 寻找数组中每个元素的下一个更大元素
 * @param nums 输入数组
 * @return 结果数组，res[i]表示nums[i]右侧第一个比它大的元素，不存在则为-1
 */
vector<int> nextGreaterElement(const vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);  // 初始化结果为-1
    stack<int> st;  // 单调栈，存储元素索引（而非值，方便计算位置）
    
    // 遍历数组
    for (int i = 0; i < n; ++i) {
        // 当栈不为空，且当前元素大于栈顶元素对应的值时
        // 说明当前元素是栈顶元素的下一个更大元素
        while (!st.empty() && nums[i] > nums[st.top()]) {
            int idx = st.top();  // 获取栈顶元素索引
            st.pop();            // 弹出栈顶元素
            res[idx] = nums[i];  // 记录结果
        }
        // 将当前元素索引入栈，维持栈的单调性
        st.push(i);
    }
    return res;
}

/**
 * 寻找数组中每个元素的下一个更小元素
 * @param nums 输入数组
 * @return 结果数组，res[i]表示nums[i]右侧第一个比它小的元素，不存在则为-1
 */
vector<int> nextSmallerElement(const vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    stack<int> st;  // 单调栈，存储元素索引
    
    for (int i = 0; i < n; ++i) {
        // 与寻找更大元素相反，这里判断当前元素是否小于栈顶元素
        while (!st.empty() && nums[i] < nums[st.top()]) {
            int idx = st.top();
            st.pop();
            res[idx] = nums[i];
        }
        st.push(i);
    }
    return res;
}

/**
 * 计算直方图中最大矩形的面积
 * @param heights 直方图的高度数组
 * @return 最大矩形面积
 */
int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> left(n, -1);   // 每个柱子左侧第一个更小的元素索引
    vector<int> right(n, n);   // 每个柱子右侧第一个更小的元素索引
    stack<int> st;             // 单调栈
    
    // 计算左侧边界
    for (int i = 0; i < n; ++i) {
        // 栈不为空且当前高度小于等于栈顶高度时，弹出栈顶元素
        while (!st.empty() && heights[i] <= heights[st.top()]) {
            st.pop();
        }
        // 栈顶元素即为左侧第一个更小的元素
        if (!st.empty()) {
            left[i] = st.top();
        }
        st.push(i);
    }
    
    // 清空栈，用于计算右侧边界
    while (!st.empty()) {
        st.pop();
    }
    
    // 计算右侧边界
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && heights[i] <= heights[st.top()]) {
            st.pop();
        }
        if (!st.empty()) {
            right[i] = st.top();
        }
        st.push(i);
    }
    
    // 计算最大面积
    int maxArea = 0;
    for (int i = 0; i < n; ++i) {
        // 宽度 = 右侧边界索引 - 左侧边界索引 - 1
        int width = right[i] - left[i] - 1;
        int area = heights[i] * width;
        maxArea = max(maxArea, area);
    }
    
    return maxArea;
}

int main() {
    // 示例1：下一个更大元素
    vector<int> nums1 = {2, 1, 2, 4, 3};
    vector<int> res1 = nextGreaterElement(nums1);
    cout << "示例1：下一个更大元素" << endl;
    cout << "输入数组: ";
    for (int num : nums1) cout << num << " ";
    cout << endl;
    cout << "结果数组: ";
    for (int num : res1) cout << num << " ";
    cout << endl << endl;
    
    // 示例2：下一个更小元素
    vector<int> nums2 = {3, 4, 2, 7, 5};
    vector<int> res2 = nextSmallerElement(nums2);
    cout << "示例2：下一个更小元素" << endl;
    cout << "输入数组: ";
    for (int num : nums2) cout << num << " ";
    cout << endl;
    cout << "结果数组: ";
    for (int num : res2) cout << num << " ";
    cout << endl << endl;
    
    // 示例3：直方图最大矩形面积
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    int maxArea = largestRectangleArea(heights);
    cout << "示例3：直方图最大矩形面积" << endl;
    cout << "直方图高度: ";
    for (int h : heights) cout << h << " ";
    cout << endl;
    cout << "最大矩形面积: " << maxArea << endl;
    
    return 0;
}

admin

接雨水问题
使用单调递减栈存储柱子索引，当遇到更高的柱子时，计算凹槽可容纳的雨水量
核心公式：雨水量 += (左右边界最小值 - 凹槽底部高度) × 宽度
示例中数组 [0,1,0,2,1,0,1,3,2,1,2,1] 的结果为 6
每日温度问题
使用单调递减栈存储温度索引，当遇到更高温度时，计算两者的索引差（等待天数）
示例中温度数组 [73,74,75,71,69,72,76,73] 对应的等待天数为 [1,1,4,2,1,1,0,0]
左侧第一个更大元素
与 “下一个更大元素” 思路类似，但遍历方向为从左到右，寻找左侧而非右侧的更大元素
示例中数组 [5,2,6,3,1,4] 的结果为 [-1,5,-1,6,3,6]
股票价格跨度问题
计算连续几天内价格不超过当前价格的最大天数，本质是寻找左侧第一个更大元素的位置
示例中价格数组 [100,80,60,70,60,75,85] 的跨度为 [1,1,1,2,1,4,6]

[C++] 纯文本查看 复制代码

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

/**
 * 示例1：接雨水问题
 * 给定非负整数数组表示柱子高度，计算能接多少雨水
 */
int trapRainWater(const vector<int>& height) {
    int n = height.size();
    if (n <= 2) return 0; // 少于3个柱子无法接水
    
    stack<int> st; // 单调递减栈，存储柱子索引
    int water = 0;
    
    for (int i = 0; i < n; ++i) {
        // 当前柱子高度大于栈顶柱子高度时，可能形成凹槽
        while (!st.empty() && height[i] > height[st.top()]) {
            int bottom = st.top(); // 凹槽底部索引
            st.pop();
            
            if (st.empty()) break; // 没有左边界，无法形成凹槽
            
            int left = st.top(); // 左边界索引
            // 计算凹槽高度：左右边界的最小值减去凹槽底部高度
            int h = min(height[left], height[i]) - height[bottom];
            // 计算凹槽宽度：当前索引减去左边界索引再减1
            int w = i - left - 1;
            water += h * w;
        }
        st.push(i); // 当前柱子索引入栈，维持递减性
    }
    return water;
}

/**
 * 示例2：每日温度问题
 * 计算每个温度需要等待几天才会出现更高的温度
 */
vector<int> dailyTemperatures(const vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> res(n, 0); // 结果数组，默认0（没有更高温度）
    stack<int> st; // 单调递减栈，存储温度索引
    
    for (int i = 0; i < n; ++i) {
        // 当前温度高于栈顶温度时，计算等待天数
        while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
            int prev_idx = st.top(); // 之前的温度索引
            st.pop();
            res[prev_idx] = i - prev_idx; // 天数差
        }
        st.push(i);
    }
    return res;
}

/**
 * 示例3：找出数组中每个元素的左侧第一个更大元素
 * 与之前的"下一个更大元素"方向相反
 */
vector<int> leftGreaterElement(const vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1); // 初始化结果为-1
    stack<int> st; // 单调递减栈，存储元素索引
    
    // 从左到右遍历，寻找左侧更大元素
    for (int i = 0; i < n; ++i) {
        // 弹出栈中所有小于当前元素的索引
        while (!st.empty() && nums[st.top()] < nums[i]) {
            st.pop();
        }
        // 栈顶元素即为左侧第一个更大元素
        if (!st.empty()) {
            res[i] = nums[st.top()];
        }
        st.push(i); // 当前元素入栈
    }
    return res;
}

/**
 * 示例4：股票价格跨度问题
 * 对于每一天，返回过去几天（包括当天）中价格小于等于当天价格的最大连续天数
 */
vector<int> stockSpan(const vector<int>& prices) {
    int n = prices.size();
    vector<int> res(n, 1); // 至少包含当天，初始为1
    stack<int> st; // 单调递减栈，存储价格索引
    
    for (int i = 0; i < n; ++i) {
        // 弹出所有价格小于等于当前价格的索引
        while (!st.empty() && prices[st.top()] <= prices[i]) {
            st.pop();
        }
        // 计算跨度：如果栈为空，跨度为i+1；否则为i - 栈顶索引
        res[i] = st.empty() ? (i + 1) : (i - st.top());
        st.push(i);
    }
    return res;
}

// 打印数组辅助函数
void printArray(const vector<int>& arr, const string& name) {
    cout << name << ": ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    // 测试示例1：接雨水
    vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << "示例1：接雨水" << endl;
    printArray(height, "柱子高度");
    cout << "能接的雨水量：" << trapRainWater(height) << endl << endl;
    
    // 测试示例2：每日温度
    vector<int> temps = {73, 74, 75, 71, 69, 72, 76, 73};
    cout << "示例2：每日温度" << endl;
    printArray(temps, "温度数组");
    vector<int> days = dailyTemperatures(temps);
    printArray(days, "等待天数");
    cout << endl;
    
    // 测试示例3：左侧第一个更大元素
    vector<int> nums3 = {5, 2, 6, 3, 1, 4};
    cout << "示例3：左侧第一个更大元素" << endl;
    printArray(nums3, "输入数组");
    vector<int> leftGreater = leftGreaterElement(nums3);
    printArray(leftGreater, "结果数组");
    cout << endl;
    
    // 测试示例4：股票价格跨度
    vector<int> prices = {100, 80, 60, 70, 60, 75, 85};
    cout << "示例4：股票价格跨度" << endl;
    printArray(prices, "股票价格");
    vector<int> spans = stockSpan(prices);
    printArray(spans, "价格跨度");
    
    return 0;
}