单调栈简介

单调栈的本质是栈，使用了一些逻辑，使得栈中的元素是单调的，可以是递增也可以是递减，常用来处理下一个更大的元素问题
图片.png

单调栈实例

496. 下一个更大元素 I

图片.png
图片.png

对于nums2, 采用一个单调栈来维护，使得从后往前遍历nums时，栈中的元素从栈顶到栈底是递增的，栈顶的元素最小，栈底的元素最大，同时使用一个map记录当前元素x的右边第一个比它的元素是什么 对于1 3 4 2来说，2—>-1 4—>-1 3—>4 1—>3 由于nums1中元素都在nums2中出现，之后遍历nums1中元素只需要通过map获得即可

  1. class Solution {
  2. public:
  3.     vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
  4.         vector<int> ans(nums1.size());
  5.         stack<int> st;
  6.         map<int,int> mp;
  7.         int sz1=nums1.size(),sz2=nums2.size();
  8.         for(int i=sz2-1;i>=0;i--)
  9.         {
  10.             while(!st.empty()&&nums2[i]>=st.top())//从栈中寻找比当前元素大的
  11.                 st.pop();
  12.             mp[nums2[i]]=st.empty()?-1:st.top();//找不到则是-1 找打则使用栈顶元素
  13.             st.push(nums2[i]);
  14.         }
  15.         for(int i=0;i<sz1;i++)
  16.             ans[i]=mp[nums1[i]];
  17.         return ans;
  20.     }
  21. };
  22. //O(nums1.size()+nums2.size())
  23. //O(nums2.size())

739. 每日温度

图片.png

依然采用和上面一题相似的单调栈模板，需要改动的一点是栈中保存的不再是元素，而是元素的下标

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size());
        stack<int> st;
        for(int i=temperatures.size()-1;i>=0;i--)
        {
            while(!st.empty()&&temperatures[i]>=temperatures[st.top()])
                st.pop();
            ans[i]=st.empty()?0:st.top()-i;
            st.push(i);//将索引入栈
        }
        return ans;

    }
};
//O(n)
//O(n)

503. 下一个更大元素 II

图片.png

这一题和496题的区别在于这一题可以循环地搜索数组，即数组可以看成是循环的 比如1 2 1可以看成1 2 1 1 2 1因此第2个1后面还有1个比它大的元素2 可以将数组长度加倍并对下标进行取余操作来实现

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n=nums.size();
        vector<int> ans(n);
        stack<int> st;
        for(int i=2*n-1;i>=0;i--)
        {
            while(!st.empty()&&nums[i%n]>=st.top())
                st.pop();
            ans[i%n]=st.empty()?-1:st.top();
            st.push(nums[i%n]);
        }
        return ans;
    }
};
//O(n)
//O(n)

316. 去除重复字母

图片.png

  1. 通过应该inStack[]数组标记，使得栈中元素唯一
  2. 使用栈这种结构，保证了字符的相对位置没有改变
  3. 使用一个count[]数组计数和pop操作，保证栈中的元素字典序最小
class Solution {
public:
    string removeDuplicateLetters(string s) {
        stack<char> st;
        bool inStack[26];//记录字母是否已经在栈中
        memset(inStack,false,sizeof(inStack));
        int count[26];//记录s中各个字母出现的次数
        memset(count,0,sizeof(count));
        for(char c:s)
            count[c-'a']++;
        for(char c:s)
        {
            count[c-'a']--;
            if(inStack[c-'a'])//当前字母已经在栈中 后面直接跳过
                continue;
            while(!st.empty()&&st.top()>c)//弹出栈中的字典序在c后面的字符
            {
                //bcac  当栈中元素是bc时 遇到了a 此时只应该弹出c b不能弹出 因为b后面不会再出现
                if(count[st.top()-'a']==0)//如果当前栈顶字符后面不会再出现 则停止弹出
                    break;
                inStack[st.top()-'a']=false;//弹出的字符标记不再栈中
                st.pop();
            }
            inStack[c-'a']=true;//c入栈
            st.push(c);
        }
        string ans;
        while(!st.empty())
        {
            ans+=st.top();
            st.pop();
        }
        reverse(ans.begin(),ans.end());
        return ans;

    }
};
//O(n) 遍历字符串一次
//O(1) 最多26个字符

class Solution {
    public String removeDuplicateLetters(String s) {
        LinkedList<Character> st=new LinkedList<>();
        boolean inStack[]=new boolean[26];
        int count[]=new int[26];
        for(int i=0;i<s.length();i++)
            count[s.charAt(i)-'a']++;
        for(int i=0;i<s.length();i++)
        {
            char c=s.charAt(i);
            count[c-'a']--;
            if(inStack[c-'a']==true)
                continue;
            while(!st.isEmpty()&&st.peek()>c)
            {
                if(count[st.peek()-'a']==0)
                    break;
                inStack[st.pop()-'a']=false;

            }
            st.push(c);
            inStack[c-'a']=true;
        }
        StringBuilder sb=new StringBuilder();
        while(!st.isEmpty())
            sb.append(st.pop());
        return sb.reverse().toString();

    }
}

单调队列实例

239. 滑动窗口最大值

图片.png

维护一个队列，使得队列中的元素是递减的，队首元素是当前窗口内的最大元素，队列中的第2个元素是当前窗口中的第2大元素（如果有的话） 比如 1 2 3， 加入队列中队列中实际上只有1个元素3， 而对于3 2 1，加入队列中队列中实际上有13个元素3 2 1

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
         vector<int> ans(nums.size()-k+1);
         deque<int> q;//单调队列  队首元素最大
         //先加入k个元素 
         for(int i=0;i<k;i++)
         {
            while(!q.empty()&&q.back()<nums[i])
                q.pop_back();
             q.push_back(nums[i]);
         }
         ans[0]=q.front();//a[0]保存前k个元素中的最大元素
         //下面解决[k,nums.size()-1]区间内的元素
        for(int i=k;i<nums.size();i++)
        {
            //toAdd 当前加入的元素是nums[i]
            //因为前面的窗口中已经有了k个元素 因此有加入必然有删除
            //删除的元素是nums[i-k]
            int toAdd=nums[i],toDelete=nums[i-k];
            while(!q.empty()&&q.back()<toAdd)
                q.pop_back();//比较当前加入的元素和队列中元素大小 直到找到一个比当前元素大的或等于的
            //不能完全大于  比如2 2 2 2....当k=3时，队列中应该是2 2 2；而不是只有1个2
            q.push_back(toAdd);//队列中加入当前元素
            if(toDelete==q.front())//如果待删除的元素是队列中的最大元素 则移除队首元素
                q.pop_front();
            ans[i-k+1]=q.front();//结果保存当前窗口中的最大元素


        }
         return ans;


    }
};
//O(n)  每个元素最多入队出队1次
//O(k)  队列中最多存储k个元素