思路:
题目的主要信息:
- 入栈顺序为给定的数组的顺序
- 在不打乱入栈顺序的前提下尽量做到由大到小排序输出入栈的元素
- 若无法办到,需要按字典序最大输出
无论是由大到小输出还是按字典序最大输出,都是要求大数在前,小数在后。这些元素都是按照数组顺序进栈的,何时出栈取决于它们后面是否还有比它们更大的元素进入,如果有,则它们先进栈,等后续最大元素先输出,若是无,则输出当前元素。
方法一:逆序记录后续最大元素
具体做法:
可以用一个dpmax数组,记录在第i个元素出现以后,第i到第n的最大值,仅需逆序往前比较即可得到dpmax数组。 然后遍历给定的顺序数据,如果当前元素a[i]大于dpmax[i],即是当前元素比后续所有元素都大,则该元素可以直接出栈,否则入栈等待。 最后记得要输出栈中残留的元素。
class Solution {
public:
vector<int> solve(int* a, int aLen) {
vector<int> dpmax(aLen + 1, 0); //dpmax表示第i个数出现后,其后到n为止的最大值
for(int i = aLen - 1; i > 0; i--)
dpmax[i] = max(a[i], dpmax[i + 1]); //逆向遍历才能找到dpmax
stack<int> s;
vector<int> res;
for(int i = 0; i < aLen; i++){ //遍历数组
while(!s.empty() && s.top() >= dpmax[i]){ //当前栈顶元素大于其后要出现的最大值
res.push_back(s.top()); //直接让其出栈
s.pop();
}
s.push(a[i]);
}
while(!s.empty()){ //剩余元素出栈
res.push_back(s.top());
s.pop();
}
return res;
}
};
复杂度分析:
- 时间复杂度:O(n),最坏情况全部逆序,栈中存满元素,也相当于两次循环(for一次,for结尾全部出栈一次)。
- 空间复杂度:O(n),辅助数组dpmax与栈
方法二:记忆最大值访问
具体做法:
因为给定的是1-n的数据,所有最大值必定是n,我们可以设置一个dp数组表示这个最大值是否被访问过,如果这个最大值已经被用过出栈了,我们需要递减以更新最大值,如果这个最大值没有被访问过可以直接比较栈顶元素和它的大小,当栈顶较大时,出栈即可。
class Solution {
public:
vector<int> solve(int* a, int aLen) {
stack<int> s;
int max = aLen;
vector<bool> dp(aLen + 1, false); //记录是否访问过
vector<int> res;
for(int i = 0; i < aLen; i++){
s.push(a[i]);
dp[a[i]] = true;
while(max > 0 && dp[max] == true) //当max已经出栈后,需要递减获取下面的max
max--;
while(!s.empty() && s.top() >= max){ //当前栈顶比max大或者等,出栈
res.push_back(s.top());
s.pop();
}
}
while(!s.empty()){ //剩余元素出栈
res.push_back(s.top());
s.pop();
}
return res;
}
};
复杂度分析:
- 时间复杂度:O(n),一次遍历即可
- 空间复杂度:O(n),辅助数组dp与栈