栈和排序

描述

给你一个 1 到 n 的排列和一个栈，并按照排列顺序入栈，你要在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列。排列：指 1 到 n 每个数字出现且仅出现一次
示例
输入：[2,1,5,3,4]
返回值：[5,4,3,1,2]
说明： 
操作       栈     结果
2 入栈；[2]       []
1 入栈；[2\1]     []
5 入栈；[2\1\5]   []
5 出栈；[2\1]     [5]
3 入栈；[2\1\3]   [5]
4 入栈；[2\1\3\4] [5]
4 出栈；[2\1\3]   [5,4]
3 出栈；[2\1]     [5,4,3]
1 出栈；[2]       [5,4,3,1]
2 出栈；[]        [5,4,3,1,2]


方法一

思路分析

本题需要通过示例说明进行分析，进而得到一般性的结论，分析如下：
  • 首先先将数入栈，栈顶元素为2，比较发现未入栈的元素中还有比2更大的数，因此2不能作为最大字典序中的开始元素；
  • 继续对后面数组中的元素入栈，1入栈，相同的方法与后面数组中的元素比较，比较发现未入栈的元素中还有比2更大的数
  • 继续对后面数组中的元素入栈，5入栈，相同的方法与后面数组中的元素比较，比较发现未入栈的元素中没有比5更大的数，因此5出栈，作为最大字典序中的开始元素
  • 相同的办法对数组中的元素进行操作，此时4入栈，比较发现未入栈的元素中没有比4更大的数，4出栈
  • 数组中的元素已经全部入过栈，因此根据先进后出的方法输出栈中元素，分别为3，1，2出栈
  • 总的字典序即为[5,4,3,1,2]，操作完成，输出字典序最大的出栈序列
因此我们可以得到一般性的结论：
  • 设置一个数组temp记录给定数组a从当前位置的下一位置出发到结束位置的最大元素;
  • 给定数组中的元素一次入栈，
  • 栈顶元素与给定数组中为入栈的元素进行比较，即与temp[i]比较，如果栈顶元素更大，说明该栈顶元素应该出栈，即在最大字典序中的位置；
  • 继续上述步骤，直到给定数组中的元素都进行过入栈操作，此时如果栈中元素不为空，则将栈中元素弹出，构成完整的序列，即为字典序最大的序列。
在具体求解temp数组时我们需要每次找到该元素之后的数组中的最大值，从而填充temp数组

图解

核心代码 

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int aLen) {
        // write code here
        vector<int>temp(aLen,a[aLen-1]);
        stack<int> s;
        vector<int>ans;
        for(int i=0;i<=aLen-2;i++)
        {
            temp[i]=a[i];
            for(int j=i+1;j<=aLen-1;j++)
            {
                if(temp[i]<a[j])
                    temp[i]=a[j];
            }
           
            
        }
        for(int i = 0; i < aLen; i++) 
        {
            s.push(a[i]);//数组元素入栈
            while(!s.empty() && s.top() > temp[i+1])//栈顶元素与temp[i+1]元素比较
            {
              ans.push_back(s.top());//如果栈顶元素较大，出栈
              s.pop();
            }
        }
        while(!s.empty())//所有的数入栈后，最后将栈中输出
        {
    	  ans.push_back(s.top());
    	  s.pop();
        }
        return ans;
    }
};
复杂度分析
  • 时间复杂度：首先需要填充temp数组，从开始位置的下一个位置出发到结束位置寻找最大值，所需时间复杂度为$O(n+n-1+n-2+n-3+...+2+1)$，时间复杂度为$O(n^2)$，接着需要遍历一次数组，所需时间复杂度为$O(n)$，因此总的时间复杂度为$O(n^2)$
  • 空间复杂度：借助于一个数组用于存放未入栈元素的最大值，设置一个栈空间，大小为n，空间复杂度为$O(n)$

方法二

思路分析

      方法二对方法一中temp数组的求解进行优化，这里采用动态规划的思想，从后往前遍历数组，那么temp[i]=max{temp[i+1],a[i]}，此时求解temp数组的时间复杂度降低为$O(n)$

图解

核心代码 

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int aLen) {
        // write code here
        vector<int>temp(aLen,a[aLen-1]);
        stack<int> s;
        vector<int>ans;
        for(int i=aLen-2;i>=0;i--)
        {
            temp[i]=max(temp[i+1],a[i]);
        }
        for(int i = 0; i < aLen; i++) 
        {
           s.push(a[i]);
            while(!s.empty() && s.top() > temp[i+1])
            {
              ans.push_back(s.top());
              s.pop();
            }
        }
        while(!s.empty())
        {
    	  ans.push_back(s.top());
    	  s.pop();
        }
        return ans;
    }
};
复杂度分析
  • 时间复杂度：首先循环遍历一次数组a求出temp数组，利用了动态规划的思想，从后往前，时间复杂度为$O(n)$，接着对数组元素操作入栈出栈，时间复杂度为$O(n)$，因此总的时间复杂度为$O(n)$
  • 空间复杂度：需要额外设置一个temp数组存放数组a中每个位置的下一位置到结束位置的最大值，设置一个栈空间，大小为n，因此时间复杂度为$O(n)$


方法三

思路分析

接着我们使用另一种方法，注意到给定数组是1 到 n 的排列，也就是说，当前除栈顶元素外，其余未入栈元素的最大值其实是可以确定的：记录出栈元素，那么就可以计算出未入栈元素的最大值，之后将栈中元素全部输出。

核心代码 

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int aLen) {
        // write code here
        //vector<int>temp(aLen,a[aLen-1]);
        stack<int> s;
        vector<int>ans;
        int index=aLen;
        vector<int>temp(aLen+1,0);
        for(int i = 0; i < aLen; i++) 
        {
            s.push(a[i]);//数组元素入栈
            temp[a[i]]=1;
            while(index>0&&temp[index]==1) index--;//当前未入栈元素的最大值
            while(!s.empty()&&s.top()>index)//栈顶元素与未入栈元素的最大值比较
            {
              ans.push_back(s.top());//如果栈顶元素较大，出栈
              s.pop();
            }
        }
        return ans;
    }
};
复杂度分析
  • 时间复杂度：对数组元素操作入栈出栈，时间复杂度为$O(n)$
  • 空间复杂度：需要额外设置一个temp数组存放数组a中每个位置是否出栈，设置一个栈空间，大小为n，因此时间复杂度为$O(n)$