给你一个 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]
思路:如果当前要入栈的元素和之后的元素都没有栈顶元素大,则应出栈。
class Solution {
public:
/**
* 栈排序
* @param a int整型一维数组 描述入栈顺序
* @param aLen int a数组长度
* @return int整型vector
*/
vector<int> solve(int* a, int aLen) {
// 目的:元素入栈之后如果后面的数没有比栈顶大的元素,则栈顶出栈
// 1、先动态规划计算每个数及其后面最大的数
// 定义数组dp,dp[i]表示第i个元素及其之后最大的元素值
// 显然,dp数组是要从后往前填充的
// dp[n-1] = a[n-1]
// dp[i] = max(a[i], dp[i+1])
vector<int> dp(aLen, 0);
dp[aLen-1] = a[aLen-1];
for(int i=aLen-2; i>=0; --i){
dp[i] = max(a[i], dp[i+1]);
}
// 2、元素入栈时先判断栈顶元素和之后要遇到的最大值,
// 如果小于,新元素入栈
// 如果大于,栈顶弹出,继续判断栈顶
vector<int> result;
stack<int> tmpStack;
for(int i=0; i<aLen; i++){
while(!tmpStack.empty() && tmpStack.top()>dp[i]){
result.push_back(tmpStack.top());
tmpStack.pop();
}
tmpStack.push(a[i]);
}
while(!tmpStack.empty()){
result.push_back(tmpStack.top());
tmpStack.pop();
}
return result;
}
};