给你一个 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]
[1,2,3,4,5]
[5,4,3,2,1]
class Solution { public: /** * 栈排序 * @param a int整型一维数组 描述入栈顺序 * @param aLen int a数组长度 * @return int整型vector */ vector<int> solve(int* a, int aLen) { // write code here int j=0, n=aLen; vector<vector<int>> mr(n, vector<int>(2, 0)); int Max = INT_MIN; for(int i=n-1; i>=0; i--) { if(Max<a[i]) { Max = a[i]; j = i; } mr[i][0] = Max; mr[i][1] = j; } stack<int> st; vector<int> ans; for(int i=0; i<n; i++) { st.push(a[i]); if(i==mr[i][1]) { ans.push_back(st.top()); st.pop(); while(!st.empty() && i<n-1 && st.top()>mr[i+1][0]) { ans.push_back(st.top()); st.pop(); } } } while(!st.empty()) { ans.push_back(st.top()); st.pop(); } return ans; } };
public int[] solve (int[] a) { int n=a.length; Stack<Integer>stack=new Stack<>(); int[]dp=new int[n]; dp[n-1]=a[n-1]; for(int i=n-2;i>=0;i--) dp[i]=Math.max(dp[i+1],a[i]); //用一个数组记录第i个及之后最大元素 int[]res=new int[n]; int j=0; for(int i=0;i<n;i++){ stack.push(a[i]); while(!stack.isEmpty()&&i<n-1&&stack.peek()>=dp[i+1]) res[j++]=stack.pop();//如果栈顶元素比后面的都大,那么出栈 } while(!stack.isEmpty()) res[j++]=stack.pop(); //最后在栈中的按顺序弹出 return res; }
import java.util.*; public class Solution { public int[] solve (int[] a) { int[] rMax = new int[a.length]; // 当前位置之后的最大值(包括当前位置) rMax[a.length - 1] = a[a.length - 1]; for (int i = a.length - 2; i >= 0 ; i--) { rMax[i] = Math.max(rMax[i + 1], a[i]); } int index = 0; int[] res = new int[a.length]; Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < a.length; i++) { while (!stack.isEmpty() && stack.peek() > rMax[i]) { // 若栈顶比右侧大,则弹出 res[index++] = stack.pop(); } stack.push(a[i]); } while (!stack.isEmpty()) { res[index++] = stack.pop(); } return res; } }
class Solution { public: /** * 栈排序 * @param a int整型一维数组 描述入栈顺序 * @param aLen int a数组长度 * @return int整型vector */ vector<int> solve(int* a, int aLen) { // write code here stack<int> s; vector<int> res; vector<bool> f(aLen + 1, false); int now = aLen; for(int i = 0; i < aLen; i ++){ s.push(a[i]); f[a[i]] = true; while(now > 0 && f[now])now --; while(!s.empty() && s.top() > now){ res.push_back(s.top()); s.pop(); } } return res; } };
import java.util.*; public class Solution { /** * 栈排序 * @param a int整型一维数组 描述入栈顺序 * @return int整型一维数组 */ public int[] solve (int[] a) { // write code here //保存要返回的值 int arr[]=new int[a.length]; //创建集合保存结果 ArrayList<Integer> list = new ArrayList<>(); //创建栈 Stack<Integer> stack = new Stack<>(); stack.push(a[0]); for (int i = 1; i < a.length; i++) { int max = max(a, i); //栈顶元素小于后面最大值,就入栈 if (stack.peek() < max) { stack.push(a[i]); } else { //栈顶元素大于后面最大值,说明已经找到最大的,就出栈 //循环遍历,直到栈顶比后面最大值还小 while(!stack.isEmpty()&&stack.peek()>max){ list.add(stack.pop()); } stack.push(a[i]); } } //将值添加到数组并返回 while(!stack.isEmpty()){ list.add(stack.pop()); } for(int i=0;i<list.size();i++){ arr[i]=list.get(i); } return arr; } public int max(int [] arr, int index) { int max = Integer.MIN_VALUE; for (int i = index; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } return max; } }
import java.util.*; public class Solution { /** * 栈排序 * @param a int整型一维数组 描述入栈顺序 * @return int整型一维数组 */ public int[] solve (int[] a) { // write code here int n = a.length; Deque<Integer> stack = new ArrayDeque<>(); int[] maxArr = new int[n]; // 倒叙记录每个位置元素后面出现的最大元素 maxArr[n-1] = Integer.MIN_VALUE; int tempMax = Integer.MIN_VALUE; for(int i=a.length-2;i>=0;i--){ maxArr[i] = Math.max(a[i+1], maxArr[i+1]); } for(int i=0;i<n;i++){ System.out.print(maxArr[i]+" "); } int[] ans = new int[n]; int index = 0; for(int i=0;i<n;i++){ if(a[i] > maxArr[i]){ // 当前入栈元素大于将要入栈的元素 ans[index++] = a[i]; while(!stack.isEmpty() && stack.peek()>maxArr[i]){ ans[index++] = stack.pop(); } }else{ stack.push(a[i]); } } while(!stack.isEmpty()){ ans[index++] = stack.pop(); } return ans; } }
# # 栈排序 # @param a int整型一维数组 描述入栈顺序 # @return int整型一维数组 # class Solution: def solve(self , a ): # write code here n, stack, dp, res = len(a), [], [0]*len(a), [] dp[-1] = a[-1] # 记录从第i个元素开始到最后的最大元素 for i in range(n-2, -1, -1): dp[i] = max(dp[i+1], a[i]) for i in range(n): stack.append(a[i]) while stack and i < n-1 and stack[-1]>=dp[i+1]: res.append(stack.pop()) # 如果栈顶元素比后面所有元素都大,则弹出 while stack: res.append(stack.pop()) return res
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> res; stack<int> aux; int i=0; aux.push(a[i++]); while (aux.size()||i<=aLen){ if(i==aLen){ while(aux.size()){ res.push_back(aux.top()); aux.pop(); } i++; } else{ if(aux.size()){ int top=aux.top(); int next_max=*(std::max_element(a+i,a+aLen)); while(top>next_max){ aux.pop(); res.push_back(top); if(aux.size()) top=aux.top(); else break; } } aux.push(a[i++]); } } return res; } };
public static int[] solve(int[] a) { if (a == null || a.length == 0) { return a; } int index = 0, n = a.length; int Max = Integer.MIN_VALUE; int[][] maxarr = new int[n][2]; for (int i = n - 1; i >= 0; i--) { if (a[i] > Max) { Max = a[i]; index = i; } maxarr[i][0] = Max; maxarr[i][1] = index; } Stack<Integer> stack = new Stack<>(); ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < n; i++) { stack.push(a[i]); if (maxarr[i][1] == i) { list.add(stack.pop()); while (!stack.isEmpty() && i < n - 1 && stack.peek() > maxarr[i + 1][0]) { list.add(stack.pop()); } } } while (!stack.isEmpty()) { list.add(stack.pop()); } int[] res = new int[a.length]; for (int i = 0; i < list.size(); i++) { res[i] = list.get(i); } return res; }
public static int[] solve (int[] a) { // write code here Stack<Integer> stat=new Stack<Integer>(); int len=a.length; int rmax[]=new int[len+1]; rmax[len]=0; int[] result=new int[len]; if(len==0){ return result; } int p=0; for(int i=len-1;i>=0;i--){ rmax[i]=Integer.max(a[i],rmax[i+1]); } for(int j=0;j<a.length;j++){ while(!stat.isEmpty()&&stat.peek()>=rmax[j]){ result[p++]=stat.pop(); } stat.push(a[j]); } while(!stat.isEmpty()){ result[p++]=stat.pop(); } return result; }