题解 | #栈和排序#
栈和排序
http://www.nowcoder.com/practice/95cb356556cf430f912e7bdf1bc2ec8f
栈和排序
描述
给你一个 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)$
