Mute

个人技术博客

0%

单调栈

发表于 分类于

单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。

分类：

单调栈分为单调递增栈和单调递减栈。

单调递增栈即栈内元素保持单调递增的栈，单调递减栈即栈内元素保持单调递减的栈。

操作规则：

以单调递增栈为例：

如果新的元素比栈顶元素大，就入栈。

如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小。

效果：

加入这样一个规则之后：

栈内的元素是递增的。

当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素。

当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素。

应用：

用 O(N) 复杂度的一重遍历找到每个元素前后最近的更小/大元素位置。

伪代码：

1
2
3
4
5
6
7
stack<int> stk;
for(int i = 0; i < nums.size(); i++){
	while(!st.empty() && st.top() > nums[i]){
		st.pop();
	}
	stk.push(nums[i]);
}

LeetCode 739题 每日温度：

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n,0);
        stack<int> stk;
        for(int i = 0; i < n; i++){
            while(!stk.empty()&&temperatures[i] > temperatures[stk.top()]){//当前元素大于栈顶元素
                int cur = stk.top();  //记录栈顶元素(索引)
                res[cur] = i - cur;   //当前索引减去栈顶索引就是对应的栈顶索引会有更高温度出现的天数
                stk.pop(); //栈顶元素出栈
            }
            stk.push(i); //当前元素(索引)入栈
        }
        return res;
    }