栈和队列

1，栈

例1 直方图最大矩形

思路：用一个栈来保存下标，并保证栈中下标对应元素是非降的：某一元素>=栈顶，进栈；某一元素<栈顶，栈顶出栈，并且计算栈顶对应的面积，更新最大值。

面积的计算（栈顶出栈后）：
L=新栈顶+1（栈不空）；L=0（栈空）；
R=该元素-1；
面积=（R-L+1）*height；
为保证最后所有元素都能出栈（出栈时才计算面积），最后压入一个0。

class Solution {
public:
    int largestRectangleArea(vector<int> &height) 
    {
        int max_area=0;
        stack<int> stk;
        height.push_back(0);//数组最后补一个0

        for(int i=0;i<height.size();i++)
        {
            if(stk.empty()||height[stk.top()]<=height[i])
                stk.push(i); //保存下标
            else
            {
                //栈顶出栈，计算面积,不断出栈，直到满足入栈条件
                while(!stack.empty() && height[stk.top()]>height[i]){
                    int temp=stk.top();
                    stk.pop();
                    int cur_area=height[temp] * (stk.empty() ? i:(i-stk.top()-1));
                    max_area=max(max_area,cur_area);
                }
            }
        }
        return max_area;    
    }
};

2，队列

例1 滑动窗口中的最大值

思路：维护一个递减的双端队列，队首为当前窗口的最大值，后面元素为候选的最大值。
窗口滑动时，先判断队首是否会滑出窗口，若是，队首出队；
新进入窗口的值为b，b一定会入队，并且入队前要把队尾那些比b小的元素删除掉。

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int k)
    {
        vector<int> ans;
        deque<int> d;

        //初始化队列，k=5，a[0...4]={1,2,3,2,1}时，得到的队列为{3,2,1}
        int i;  
        for(i=0;i<k;i++){ 
            while(!d.empty() && d.back()<=num[i])
                d.pop_back();
            d.push_back(num[i]);
        }

        ans.push_back(d.front());
        
        for(;i<len;i++){
            if(num[i-k]==d.front()) //若队首滑出窗口
                d.pop_front();
            while(!d.empty() && d.back()<=num[i]) //num[i]滑入窗口，入队
                d.pop_back();
            d.push_back(num[i]);
            ans.push_back(d.front());
        }

        return ans;

    }
};