跳到主要内容

monotonic-stack

0. 说明

  • 此章节代码主要使用cpp
  • 本章节代码题目来源主要为leetcode，代码模式与leetcode类似。

1. 简单介绍

在算法和数据结构中，单调栈是一种非常实用的技巧。它并不是一种新的数据结构，而是对普通栈的一种使用策略——通过维护栈内元素的单调性（递增或递减），高效地解决一类“寻找最近更大/更小元素”的问题。

核心思想： 当我们遍历数组时，如果当前元素破坏了栈的单调性，就不断弹出栈顶元素，直到满足单调性为止，再将当前元素入栈。 这个“弹出”的过程，往往就是我们找到答案的关键时刻。

单调栈严格来讲并不能算是一种算法或者数据结构，应该算是一种使用技巧。故此处不再赘述，直接使用题目来进行学习练习。

2. 题目实战练习

2.1 每日温度​

link:每日温度 解答代码入下：

class Solution 
{
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) 
    {    
        int n=temperatures.size();
        vector<int> ans(n,0);
        stack<int> stk;
        for (int i = 0; i < n; ++i) 
        {
            while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) 
            {
                int prevIndex = stk.top();
                stk.pop();
                ans[prevIndex] = i - prevIndex; 
            }
            stk.push(i); 
        }
        return ans;
    }
};