「LeetCode」Monotone Stack - 单调栈

2020-04-13
摘要: 简单介绍单调栈及其性质与应用。单调栈就是满足单调性的栈结构。在每次插入新的元素时,弹出个数尽量少的元素来保持栈的单调性。

##定义

单调栈就是满足单调性的栈结构。在每次插入新的元素时,弹出个数尽量少的元素来保持栈的单调性。

例如,以递增的单调栈举例,栈中自顶向下的元素为 $1,10,50,70$ 时 ,插入元素 $40$ 时为了保证单调性需要依次弹出元素 $50, 70$,操作后栈变为 $1, 10, 40$。

// Insert element x
while(!s.empty() && x > monoStack.top()) {
    s.pop();
}
s.push(x);

由于栈的操作是线性 $O(n)$ 的,因此可以借助它的性质高效地解决许多问题。

性质#

### 不弹出相等元素

首先压入元素时,递增的单调栈总是弹出比自己大的元素,递减的单调栈总是弹出比自己小的元素。以下性质描述采用不弹出相等元素的情况

  1. 对于递增的单调栈来说,如果从左至右遍历数组并将元素入栈,在完成 pop 操作后,栈顶则为左侧第一个比新元素小或者相等的元素

    1. 或者说,对于正被 pop 的元素来说,它遇到了右侧第一个比自己的元素。
    2. 或者说,对于栈内的所有元素,与其相邻的左侧元素则为第一个比自己小或者相等的元素。
  2. 对于递减的单调栈来说,如果从左至右遍历数组并将元素入栈,在完成 pop 操作后,栈顶则为左侧上第一个比新元素大或者相等的元素

    1. 或者说,对于正被 pop 的元素来说,它遇到了右侧第一个比自己的元素。
    2. 或者说,对于栈内的所有元素,与其相邻的左侧元素则为第一个比自己大或者相等的元素。

弹出相等元素#

如果采用弹出相等元素的方式,只是交换了一下左右侧遇到的数的情况:

  1. 对于递增的单调栈来说,如果从左至右遍历数组并将元素入栈,在完成 pop 操作后,栈顶则为左侧第一个比新元素小的元素

    1. 或者说,对于正被 pop 的元素来说,它遇到了右侧第一个比自己小或者相等的元素。
    2. 或者说,对于栈内的所有元素,与其相邻的左侧元素则为第一个比自己**小的元素。
  2. 对于递减的单调栈来说,如果从左至右遍历数组并将元素入栈,在完成 pop 操作后,栈顶则为左侧上第一个比新元素大的元素

    1. 或者说,对于正被 pop 的元素来说,它遇到了右侧第一个比自己大或者相等的元素。
    2. 或者说,对于栈内的所有元素,与其相邻的左侧元素则为第一个比自己的元素。

应用#

概述#

单向查找#

考虑上述性质,单调栈非常适合解决寻找单侧某个方向上第一个比自己大/小(或者相等)的元素的问题。如 POJ3250 Bad Hair Day腾讯 2020 后台校园招聘试题LeetCode 739. Daily TemperaturesLeetCode 503. Next Greater Element II 等。注意,这些问题都是单向寻找

双向查找#

某些问题需要找到两侧第一个比自己大/小的元素。但考虑单调栈的性质,必然是一侧有等号,一侧没有等号,理论上无法直接找到两侧的第一个数。我们可以通过:

  1. 不弹出相等的元素,利用支持随机访问的 vector 构造栈,再通过向前寻找栈内第一个不相等元素来达到目的。
  2. 根据具体题目,判断重复元素被多次考虑是否影响答案(大部分情况都不影响)。若不影响答案,则无所谓。
    1. 比如 LeetCode 84. Largest Rectangle in HistogramPOJ2796 Feel Good,由于我们计算的是最大值,因此重复计算相等的元素(无论是在哪侧)并不会影响答案(每次计算都会有新的接近答案的值覆盖旧值)。
    2. 比如 LeetCode 42. Trapping Rain Water,遇到相等的元素(无论是哪侧)时计算出”积水”的高度为 $0$,因此也不影响”积水”的总体积。
    3. 比如LeetCode 907. Sum of Subarray Minimums,遇到相等的元素(无论是哪侧重复),计算的区间都是独立的,因此不影响答案。

例题#

  • 如例题 POJ3250 Bad Hair Day,可以借助找到前向中第一个比自己大的元素,来计算其间有多少个比自己小的元素。
  • 如例题 LeetCode 84. Largest Rectangle in Histogram,可以针对每个位置的柱子找到左右两侧第一个比自己小的元素,来计算以其为顶的矩形的面积。这可以通过构造一个单调递增的单调栈来做到。回顾上面的性质,我们选择在元素被弹出时来计算面积,因为此时它遇到了右侧第一个比自己大的元素,同时也可以直接得到左侧第一个比它大的元素(相邻元素)。这一题也被一些人总结为:求子数组中的最小值乘以子序列的长度的最大值。
    • 对于这题来说,有一个小技巧,那就是在开头和结尾增加两个 dumb 值,也就是增加两个 $0$,这样可以非常方便地处理在左侧找不到比其小的值,或者最后栈内元素未弹出而导致未计算的情况。注意,若开头增加 $0$,那么判断条件中就不能出现 $=$,否则结尾的 $0$ 会使其出栈;若需要 $=$ 来优化空间,可以考虑修改开头的 $0$ 为 $-1$;另外在开头插入 $0$ 会牺牲 $O(n)$ 的时间,所以一般只在结尾插入 $0$,在开头做特判。
    • 例题 LeetCode 85. Maximal Rectangle 为在其基础上的拓展。将二位矩阵看作是”叠加”的楼层/柱子,即可解决问题。
  • 如例题 POJ2796 Feel Good,可以针对每个位置的数找到找到左右两侧第一个比自己小的元素,来计算以其为最小值的区间。同样地:这可以通过构造一个单调递增的单调栈来做到。我们选择在元素被弹出时来计算答案,因为此时它遇到了右侧第一个比自己大的元素,同时也可以直接得到左侧第一个比它大的元素(相邻元素)。这一题也被一些人总结为:求子数组中的最小值乘以子数组元素和的最大值。
    • 同样地,利用 dumb 值可以帮助我们简化代码。
  • 如例题 LeetCode 907. Sum of Subarray Minimums,题意为寻找连续子数组中的最小值的和。我们从另一个角度考虑(而不是考虑遍历所有子数组),针对每个下标为 $i$ 的数,寻找左右两侧第一个比它小的数,下标分别为 $j,k$,那么它就是 $(i-j)*(k-i)$ 个连续子数组的最小值。值得思考的是相同的数应该如何处理?如果他们在同一区间内,则不应该被重复处理(判断时加上 $=$ 另其出栈即可) ;如果他们不在一个区间内,则不用管它。

还有一个有趣的性质,顺序遍历数组将元素压入递减单调栈时,在考虑当前元素前,栈中的元素个数等于在当前位置向前看,能够”看到”的元素的个数。如例题 腾讯 2020 后台校园招聘试题,便是直接利用了这个性质。

注意事项#

等号的取舍#

对于单向的查找,究竟应不应该弹出相等的元素应该视具体情境做决定。如 POJ3250 Bad Hair Day 中不应该弹出,否则就意味着牛$_i$ 可以看到与自己一样高的牛。而 腾讯 2020 后台校园招聘试题 中就应该弹出相等的元素,因为相同高的楼房应该是可以相互遮挡的。

对于双向的查找,参照双向查找

存储的元素是什么#

栈中存储的不一定是元素的值,应该根据具体情境做决定。如 POJ3250 Bad Hair Day 中需要存储下标来计算下标之差,注意此时判断时不能直接和 monoStack.top() 做比较,而是和对应的值做比较。而 腾讯 2020 后台校园招聘试题 中就是直接存储元素的值,因为我们不关心下标是多少。

例题与题解#

POJ3250 Bad Hair Day#

POJ3250 Bad Hair Day

借助找到前向中第一个比自己大的元素,来计算其间有多少个比自己小的元素。

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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> heights(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> heights[i];
    }
    
    stack<int> s;
    long long ans = 0;
    for (int i = n-1; i >= 0;  --i) {
        while(!s.empty() && heights[i] > heights[s.top()]) {
            s.pop();
        }
        long long right_most = n;
        if(!s.empty()) right_most = s.top();
        ans += right_most - i - 1;
        s.push(i);
    }
    
    cout << ans << endl;
}

LeetCode 84. Largest Rectangle in Histogram#

LeetCode 84. Largest Rectangle in Histogram

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        heights.push_back(0);

        int ans = 0;
        for(int i = 0; i < heights.size(); ++i) {
            while(!s.empty() && heights[s.top()] >= heights[i]) {
                int height = heights[s.top()];
                s.pop();
                    int right = i, left = s.size() ? s.top() : -1;
                ans = max(ans, height * (right - left - 1));
            }
            s.push(i);
        }

        return ans;
    }
};

LeetCode 85. Maximal Rectangle#

LeetCode 85. Maximal Rectangle

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(!matrix.size()) return 0;
        vector<int> heights(matrix[0].size() + 1, 0);
        int ans = 0;

        for(int i = 0; i < matrix.size(); ++i) {
            for(int j = 0; j < matrix[i].size(); ++j) {
                if(matrix[i][j] == '0') heights[j] = 0;
                else heights[j] += 1;
            }
            ans = max(ans, largestRectangleArea(heights));
        }

        return ans;
    }

        // alomost the same...
    int largestRectangleArea(vector<int> &heights) {
        int ans = 0;
        stack<int> s;
        for(int i = 0; i < heights.size(); ++i) {
            while(!s.empty() && heights[s.top()] >=  heights[i]) {
                int height = heights[s.top()];
                s.pop();
                int right = i, left = s.size() ? s.top() : -1;
                ans = max(ans, height * (right - left  - 1));
            }
            s.push(i);
        }

        return ans;
    }
};

POJ2796 Feel Good#

POJ2796 Feel Good

#include <iostream>
#include <stdio.h>
#include <stack>
#include <vector>

using namespace std;

int main() {
    int n;
    while(cin >> n) {
        vector<int> values(n+1, 0); // n+1!
        vector<long long> sum(n, 0);
        
        scanf("%d", &values[0]);
        sum[0] = values[0];
        for(int i = 1; i < n; ++i) {
            scanf("%d", &values[i]);
            sum[i] = values[i] + sum[i-1];
        }
        
        stack<int> s;
        long long ans = 0;
        int l = 1, r = 1;
        for(int i = 0; i < values.size(); ++i) {
            while(!s.empty() && values[s.top()] >= values[i]) {
                int smallest = values[s.top()], left = 1, right = i;
                long long localSum = sum[i - 1];
                s.pop();
                
                  // if there exists a left boundary, then update left and localSum
                if(!s.empty()) {
                    left = s.top() + 2; // +2!
                    localSum -= sum[s.top()]; 
                }
                
                long long res = localSum * smallest;
                if(res > ans) {
                    ans = res;
                    l = left;
                    r = right;
                }
            }
            s.push(i);
        }
        
        cout << ans << endl << l << " " << r << endl;
    }
}

逛街 - 腾讯 2020 后台校园招聘试题#

腾讯 2020 后台校园招聘试题

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

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> heights(n, 0);
    vector<int> counts(n, 1);
    for (int i = 0; i < n; ++i) {
        cin >> heights[i];
    }
    
    stack<int> s1, s2;
    for(int i = 0; i < n; ++i) {
        counts[i] += s1.size();
        while(!s1.empty() && s1.top() <= heights[i]) {
            s1.pop();
        }
        s1.push(heights[i]);
      
        counts[n-1-i] += s2.size();
        while(!s2.empty() && s2.top() <= heights[n-1-i]) {
            s2.pop();
        }
        s2.push(heights[n-1-i]);
    }
    
    for (int i = 0; i < n; ++i) {
        cout << counts[i] << " ";
    }
    cout << endl;
}

LeetCode 42. Trapping Rain Water - 接雨水#

42. Trapping Rain Water

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> s;
        int ans = 0;
        for(int i = 0; i < height.size(); ++i) {
            while(!s.empty() && height[s.top()] < height[i]) {
                int currentHeight = height[s.top()];
                s.pop();

                if(s.empty()) break;

                int right = i, left = s.top();
                int h = min(height[right], height[left]) - currentHeight;
                ans += h * (right - left - 1);
            }
            s.push(i);
        }

        return ans;
    }
};

LeetCode 907. Sum of Subarray Minimums - 子数组的最小值之和#

907. Sum of Subarray Minimums

class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        const int MOD = 1e9+7;
        A.push_back(0);
        stack<int> s;
        int ans = 0;
        for(int i = 0; i < A.size(); ++i) {
            while(!s.empty() && A[s.top()] >= A[i]) {
                int minIndex = s.top();
                int current = A[minIndex];
                s.pop();
                int left = s.empty() ? -1 : s.top(), right = i;
                (ans += ((right - minIndex)*(minIndex - left)%MOD * current)%MOD) %= MOD;
            }
            s.push(i);
        }

        return ans;
    }
};

LeetCode 739. Daily Temperatures - 每日温度#

LeetCode 739. Daily Temperatures

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

        return ans;
    }
};

LeetCode 503. Next Greater Element II - 下一个更大元素 II#

503. Next Greater Element II

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);
        
        stack<int> s;
        int time = 2;
        while(time--) {
            for(int i = 0; i < n; ++i) {
                while(!s.empty() && nums[s.top()] < nums[i]) {
                    ans[s.top()] = nums[i];
                    s.pop();
                }
                s.push(i);
            }
        }
        
        return ans;
    }
};

LeetCode 496. Next Greater Element I - - 下一个更大元素 I#

LeetCode 496. Next Greater Element I

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        vector<int> ans(n1, -1);
        unordered_map<int, int> res;

        stack<int> s;
        for(int i = 0; i < n2; ++i) {
            while(!s.empty() && nums2[s.top()] < nums2[i]) {
                res[nums2[s.top()]] = nums2[i];
                s.pop();
            }
            s.push(i);
        }

        for(int i = 0; i < n1; ++i) {
            if(res.count(nums1[i])) ans[i] = res[nums1[i]];
        }

        return ans;
    }
};

LeetCode 1019. Next Greater Node In Linked List - 链表中的下一个更大节点#

LeetCode 1019. Next Greater Node In Linked List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> nums;
        while(head) {
            nums.push_back(head->val);
            head = head->next;
        }

        int n = nums.size();
        vector<int> ans(n, 0);

        stack<int> s;
        for(int i = 0; i < n; ++i) {
            while(!s.empty() && nums[s.top()] < nums[i]) {
                ans[s.top()] = nums[i];
                s.pop();
            }
            s.push(i);
        }

        return ans;
    }
};