单调栈

leetcode 496 503 556 581 84 85

滑动窗口最大值

//如果进来的元素比队头元素大，那么队头元素就出队，一直到队头比这个元素要大未知
//所以这个队列就是单调递增的
//最大的值一直在队尾
//如果尾部的值比j小那么说明滑动窗口已经过去了，所以pop_back()掉
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        int j = 0;
        vector<int> res;
        for(int i=0;i<nums.size();i++){
            while(dq.size()>0&&nums[dq.front()]<nums[i]) dq.pop_front();
            dq.push_front(i);
            if(i-j+1>k){
                if(dq.back()<=j)dq.pop_back();
                j++;
            }
            if(i+1>=k)
            res.push_back(nums[dq.back()]);
        }
        return res;
    }
};

下一个更大的元素

//从后往前如果这个值比栈中的值要大那么弹栈 否则这个值进栈
int idx[100000];

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
        stack<int> sk;
        for(int i=nums.size()-1;i>=0;i--){
            
            while(sk.size()>0&&nums[i]>nums[sk.top()]){
                sk.pop(); 
            }
            if(sk.empty()||nums[sk.top()]>nums[i]){
                
                if(sk.empty()) idx[nums[i]] = -1;
                else idx[nums[i]] = nums[sk.top()];
                sk.push(i);
            }
        }
        for(int i=0;i<findNums.size();i++){
            findNums[i] = idx[findNums[i]];
        }
        
        return findNums;
    }
};