单调栈专题

青旅半醒 2023-08-17 15:14 139阅读 0赞

问题驱动型分析博客：

题目是这样的，给一个数组，返回一个大小相同的数组。返回的数组的第i个位置的值应当是，对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素（如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上-1）。

简单的例子：

input: 5,3,1,2,4

return: -1 3 1 1 -1

BONUS：

1.add 0 is important action to make sure alll elements can out of stack

2.when we see a situation we will have a static situation in our mind.But every time different situation's variable have diifferent meaning .

ONCE AGAIN:

MAKE SURE YOU understand the meaning of the variables!!!

#include<stdio.h>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<set>
    #include<map>
    #include<algorithm>
    #include<stack>
    #include<climits>
    //monotonic stack application
    using namespace std;
    class Solution {
    public:
        int largestRectangleArea(vector<int> &height)
        {
            int res=0;
            //add 0 make sure all elements come out of the stack
            height.push_back(0);
            vector<int> index;
            for(int i=0;i<height.size();i++)
            {
                //find the max area height need to find the lowest one,if larger some part can't make this rectangle
                while(index.size()>0&&height[index.back()]>=height[i])
                {
                    int h=height[index.back()];
                    index.pop_back();
                    //if still have number in stack.Means rectangle don't start with zero,-1 is to balance
                    int sidx=index.size()>0?index.back():-1;
                    cout<<"indexback"<<index.back()<<endl;
                    cout<<"flag"<<i<<" "<<sidx<<" "<<i-sidx-1<<endl;
                    //make sure the true meaning of variable is very important.
                    /**
                    *such as this i is the point+1,sidx is the point0-1,point-point0+1==point+1-point0+1-1
                    point0&point means the rectangle's start and end
                    **/
                    res=max(res,h*(i-sidx-1));
    
                }
                index.push_back(i);
    
            }
            return res;
        }
    };
    
    int main()
    {
        vector<int> res={
        2,1,5,6,2,3};
        Solution s;
        cout<<s.largestRectangleArea(res)<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Marigolci/p/11342700.html