LeetCode——单调数据结构

总结在LeetCode中遇到的单调栈的一系列题目

单调栈

单调栈是这样的一种数据结构：栈中从栈底到栈顶的数都是递减的，为了维护这种结构在插入比当前栈顶大的数的时候都需要先将栈顶的数弹出，这样我们就能够知道弹出的这个数两边比它大的数了。在某些题目中，单调栈的这种特定能够给我们提供很大的帮助。

LeetCode 84

Largest Rectangle in Histogram

题解：

维护一个递增的单调栈，如果需要将栈顶数据弹出则表示形成了山峰的形状，这样我们就可以计算出这个山峰里能够围成的矩形的面积，因为弹出的这一个数能够知道其左右比它小的数。当遍历完以后还有一些矩形需要计算，再将这个栈依次弹出，这个时候右边没有比它小的数了，他左边比它小的数就是栈顶的数。每弹出一个数就能够计算出一个矩形的面积。

代码：

class Solution {
public:
    // 维护单调栈
    int largestRectangleArea(vector<int>& heights){
        int len = heights.size();
        stack<int> s;
        int res = 0;
        for(int i = 0; i < len; i++)
        {
            while(!s.empty() && heights[s.top()] > heights[i])
            {
                int tem = s.top();
                s.pop();
                // 计算面积
                int curArea = s.empty() ? i*heights[tem] : (i - s.top() - 1)*heights[tem];
                res = max(res, curArea);
            }
            s.push(i);
        }
        while(!s.empty())
        {
            int tem = s.top();
            s.pop();
            int curArea = s.empty() ? len*heights[tem] : (len - s.top() - 1) * heights[tem];
            res = max(res, curArea);
        }
        return res;
    }
};

LeetCode 85

Maximal Rectangle

题意：

给出一个只包含0和1的二维矩阵，求出其中1围成的矩形的最大面积

题解：

这道题可以说是上面那道题的变形，因为把这个n*m的矩阵转换成m个直方图就是上面的那道题，计算m次即可

代码：

class Solution {
public:
    vector<int> getSlice(vector<vector<char>>& matrix, int h)
    {
        vector<int> ret;
        int len = matrix[0].size();
        for(int i = 0; i < len; i++)
        {
            int tem = h, count = 0;
            while(tem >= 0 && matrix[tem][i] == '1')
            {
                tem --;
                count ++;
            }
            ret.push_back(count);
        }
        return ret;
    }
    
    int maximalRectangle(vector<vector<char>>& matrix){
        int len1 = matrix.size();
        if(len1 == 0) return 0;
        int len2 = matrix[0].size();
        if(len2 == 0) return 0;
        int res = 0;
        for(int t = 0; t < len1; t++)
        {
            vector<int> heights = getSlice(matrix, t);
            int len3 = heights.size();
            // 使用栈来保存一个递增的序列
            stack<int> s;
            int tem_res = 0;
            for(int i = 0; i < len3; i++)
            {
                while(!s.empty() && heights[s.top()] > heights[i])
                {
                    int tem = s.top();
                    s.pop();
                    // 计算不在序列内的区块的面积
                    int curArea = s.empty() ? i*heights[tem] : (i - s.top() - 1)*heights[tem];
                    tem_res = max(tem_res, curArea);
                    // cout<<i<<" "<<tem_res<<endl;
                }
                s.push(i);
            }
            // 对递增序列中的序列面积进行计算
            while(!s.empty())
            {
                int tem = s.top();
                s.pop();
                int curArea = s.empty() ? len3*heights[tem] : (len3 - s.top() - 1) * heights[tem];
                tem_res = max(tem_res, curArea);
                // cout<<tem<<" "<<tem_res<<endl;
            }
            res = max(res, tem_res);
        }
        return res;
    }
};

LeetCode 456

132 Pattern

题意：

给出一个数组，判断是否存在这样的三个数：i < j < k，同时a[i] < a[k] < a[j] 类似于132的组合

题解：

从后往前去维护一个递减的单调栈，同时记录淘汰掉的数的最大值s3（这里相当于a[k]），从后往前遍历的过程中如果有数比s3要小，则表明存在上述的结构

代码：

class Solution {
public:
    // 单调栈结构巧妙解法
    bool find132pattern(vector<int>& nums){
        stack<int> s;
        int len = nums.size();
        if (len < 3) return false;
        int s3 = INT_MIN;
        for(int i = len - 1; i >= 0; i--)
        {
            if(nums[i] < s3) return true;
            while(!s.empty() && nums[i] > s.top())
            {
                s3 = max(s3, s.top());
                s.pop();
            }
            s.push(nums[i]);
        }
        return false;
    }
};

单调队列

单调队列能够维护一个滑动窗口的最大值或者最小值

一般队列中存放的是数组中的index。以最大值为例，队列加数时：判断最后一个数是不是小于等于当前数，如果如果是就弹出最后这个数，不断重复直到无法弹出最后那个数后加当前数加入队尾，使得这个队列中是单调的。队列减数：通过index的差值判断在不在窗口内，通过差值计算是否值是否过期。

LeetCode 239

题目链接

典型的滑动窗口内的最大值问题，这里要求每一个滑动窗口的最大值并加入到一个动态数组中

class Solution {
public:
    // 单调队列数据结构
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int len = nums.size(), l = 0, r = 0;
        deque<int> de;
        vector<int> res;
        for(; r < len; r++)
        {
            while(!de.empty() && nums[r] >= nums[de.back()])
                de.pop_back();
            de.push_back(r);
            if(r >= k-1)
            {
                res.push_back(nums[de.front()]);
                if(de.front() <= l)
                    de.pop_front();
                l++;
            }
        }
        return res;
    }
};