张天昀的个人博客

单调栈算法

2019年12月04日

用处

求数组左侧/右侧比aia_i更小/更大的第一个值

42-接雨水

不断找到左边第一个比当前低的柱子,计算宽度、高度差和体积并加到答案里

class Solution {
public:
    int n;
    stack<pair<int,int>> s;
    int trap(vector<int>& h) {
        n = h.size();

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            while (!s.empty() and h[i] > s.top().second) {
                pair<int,int> p = s.top();
                s.pop();
                if (s.empty()) {
                    s.push(p);
                    break;
                }
                int x = i - s.top().first - 1;
                int y = min(s.top().second, h[i]);
                if (y < p.second) break;
                ans += x * (y - p.second);
            }
            s.push(make_pair(i, h[i]));
        }
        while (!s.empty()) s.pop();
        
        return ans;
    }
};

84-柱状图中的最大矩形

问求老题目,找到每一个元素左边第一个比它小的元素(单调递增栈)。

class Solution {
public:
    int n, ans;
    stack<pair<int,int>> s;
    int largestRectangleArea(vector<int>& heights) {
        n = heights.size(), ans = 0;
        
        heights.push_back(0);
        s.push(make_pair(-1, 0));
        for (int i = 0; i <= n; ++i) {
            while (!s.empty() and heights[i] < s.top().second) {
                int h = s.top().second;
                s.pop();
                ans = max(ans, h * (i - s.top().first - 1));
            }
            s.push(make_pair(i, heights[i]));
        }

        while (!s.empty()) s.pop();
        return ans;
    }
};

85-最大矩形

对行前缀和(?),然后每行求一次直方图中的最大矩形面积

也可以DP或者用位运算暴力。

class Solution {
public:
    int m, n;
    vector<int> h;
    int solve() {
        int ret = 0;
        stack<pair<int, int>> s;
        for (int i = 0; i < n; ++i) {
            while (!s.empty() and h[i] < s.top().second) {
                auto p = s.top();
                s.pop();
                int x = s.empty() ? i : (i - s.top().first - 1);
                int y = p.second;
                ret = max(ret, x * y);
            }
            s.push(make_pair(i, h[i]));
        }
        while (!s.empty()) {
            auto p = s.top();
            s.pop();
            int x = s.empty() ? n : (n - s.top().first - 1);
            int y = p.second;
            ret = max(ret, x * y);
        }
        return ret;
    }
    int maximalRectangle(vector<vector<char>>& matrix) {
        m = matrix.size();
        if (m == 0) return 0;
        n = matrix[0].size();
        if (n == 0) return 0;
        h.resize(n, 0);

        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') ++h[j];
                else h[j] = 0;
            }
            ans = max(ans, solve());
        }
        return ans;
    }
};

962-最大宽度坡

对每个元素找到左侧第一个不比它小(大于等于)的元素(单调递减栈)。

class Solution {
public:
    int n, ans;
    stack<pair<int,int>> s;
    int maxWidthRamp(vector<int>& A) {
        n = A.size();
        for (int i = 0; i < n; ++i) {
            if (s.empty() or A[i] < s.top().second) {
                s.push(make_pair(i, A[i]));
            }
        }
        ans = 0;
        for (int i = n-1; i >= 0; --i) {
            while (!s.empty() and A[i] >= s.top().second) {
                ans = max(ans, i - s.top().first);
                s.pop();
            }
        }
        return ans;
    }
};

1124-表现良好的最长时间段

996福报题 转化为前缀和中对每个元素找到左侧第一个比它大的元素(单调递减栈)。

class Solution {
public:
    int n;
    vector<int> p;
    stack<pair<int,int>> s;
    int longestWPI(vector<int>& hours) {
        n = hours.size();
        p.resize(n+1, 0);
        for (int i = 1; i <= n; ++i) {
            p[i] = p[i-1] + (hours[i-1] > 8 ? 1 : -1);
        }
        for (int i = 0; i <= n; ++i) {
            if (s.empty() or p[i] < s.top().second) {
                s.push(make_pair(i, p[i]));
            }
        }

        int ans = 0;
        for (int i = n; i >= 1; --i) {
            while (!s.empty() and p[i] > s.top().second) {
                ans = max(ans, i - s.top().first);
                s.pop();
            }
        }
        return ans;
    }
};