算法

单调栈总结

Posted by Meng Cao on 2019-06-01

理论

单调栈是一个维护性的数据结构，通常用于一下场景：
给定数组nums, 对于某一位置i :

  1. 找到向左数第一个比nums[i]大的位置 —> 从左向右维护一个单调递减栈；
  2. 找到向左数第一个比nums[i]小的位置 —> 从左向右维护一个单调递增栈；
  3. 找到向右数第一个比nums[i]大的位置 —> 从右向左维护一个单调递减栈；
  4. 找到向右数第一个比nums[i]小的位置 —> 从右向左维护一个单调递增栈。

从栈中元素来看，递减栈会剔除波谷，留下波峰；递增栈剔除波峰，留下波谷。
栈是否是严格递增或者严格递减，与nums中元素是否有重复无关，取决于栈中是否可以存在相同的元素。

例题

Case 1

Leetcode 42 Trapped water

思路： 由于蓄水是两高夹一底的模块，求每一个位置的蓄水量，我们需要向左向右找到最近的最大值；向右的最大值可以在向后循环中直接判断，向左的最大值通过从左向右维护一个递减栈来找到。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0, current = 0;
        stack<int> st;
        while(current < height.size()) {
            while(!st.empty() && height[current]>=height[st.top()]) {
                int top = st.top();
                st.pop();
                if(st.empty()) break;
                int distance = current - st.top() - 1;
                int bounded_height = min(height[current], height[st.top()]) - height[top];
                ans += distance * bounded_height;
            }
            st.push(current++);
        }
        return ans;
    }
};

Leetcode 901. Online Stock Span

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].
思路：这一题要求找到左边比其小的最长序列的长度。很容易被误认为是找左边第一个最小而使用递增栈。但是仔细分析，左边比其小的最长序列，其实是求左边第一个比其大的元素的位置，这之间就是所要求的序列。所以应该使用递减栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class StockSpanner {
public:
    StockSpanner() {
        
    }
    
    int next(int price) {
        int span = 1;
        while(!s_.empty() && price >= s_.top().first) {
            span += s_.top().second;
            s_.pop();
        }
        s_.emplace(price, span);
        return span;
    }
    
private:
    stack<pair<int,int>> s_;
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */

Case 2

Leetcode 84. Largest Rectangle in Histogram

思路：将问题转化为求以某一高度nums[i]为高度的矩形的最大面积，即给定高度，我们向左向右寻找边界(第一个比nums[i]小的位置)。如图：对于nums[2]=5, 左边界index为1, 右边界为4, 所以可以构成的矩形面积为nums[2]*(4-2-1). 所以这边使用单调递增栈。
这边在原序列左后增加一个0元素，可以方便处理边界(0小于序列中的所有元素，所以肯定会触发操作)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.push_back(0);
        int res = 0;
        
        for(int i=0; i<heights.size(); ++i) {
            while(!st.empty() && heights[i]<heights[st.top()]) {
                int curHeight = heights[st.top()];
                st.pop();
                int left = st.empty() ? -1 : st.top();
                res = max(res, curHeight*(i-left-1));
            }
            st.push(i);
        }
        
        return res;
    }
};

Case 3

Leetcode 496. Next Greater Element I

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]

思路：求右边第一个比nums[i]大的位置，从右向左构建一个单调递减栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        stack<int> st;
        unordered_map<int,int> indices;
        
        for(int i=nums2.size()-1; i>=0; --i) {
            while(!st.empty() && nums2[i]>st.top())
                st.pop();
            if(st.empty()) 
                indices[nums2[i]] = -1;
            else
                indices[nums2[i]] = st.top();
            st.push(nums2[i]);   
        }
        
        for(int i=0; i<nums1.size(); ++i)
            res.push_back(indices[nums1[i]]);
        
        return res;
    }
};

类似问题：
503. Next Greater Element II

739. Daily Temperatures

Case 4

做题太少，还没遇到这种类型的题目。

FEATURED TAGS
算法
FRIENDS