栈和排序

C++ 解法, 执行用时: 9ms, 内存消耗: 1528KB, 提交时间: 2021-09-13

#include <stack>

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int aLen) {
        int i,cur=0,upbd=aLen-1,*p=a;
        vector<int> res(aLen,-1);
        vector<bool> visited(aLen,false);
        stack<int> s;
        for(i=0;i<aLen;i++,p++)
        {
            s.push(*p);
            visited[(*p)-1]=true;
            for(;(upbd>=0)&&visited[upbd];upbd--);
            while((!s.empty())&&(s.top()>upbd))
            {
                res[cur]=s.top();
                cur++;
                s.pop();
            }
        }
        while((cur<aLen)&&(!s.empty()))
        {
            res[cur]=s.top();
            cur++;
            s.pop();
        }
        return res;
    }
};

C++ 解法, 执行用时: 9ms, 内存消耗: 1656KB, 提交时间: 2021-06-27

static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();
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> i_stack;
        int i = 0, val, idx;
        while(a[i] != aLen) i_stack.push( a[ i++ ] );
        res.push_back(aLen);
        while(++i < aLen)
        {
            val = INT_MIN;
            for(int j=i; j<aLen; j++)
                if(a[j] > val){ val = a[j];   idx = j; }
            if(!i_stack.empty() && i_stack.top()>val){
                do{
                    res.push_back( i_stack.top() );   i_stack.pop();
                }while(!i_stack.empty() && i_stack.top()>val);
            }
            for(int j=i; j<idx; j++) i_stack.push( a[j] );
            res.push_back(val);   i = idx;   continue;
        }
        while( !i_stack.empty() )
            { res.push_back( i_stack.top() );   i_stack.pop(); }
        return res;
    }
};

C++ 解法, 执行用时: 9ms, 内存消耗: 1904KB, 提交时间: 2021-09-10

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int n) {
      vector<int> dp(n,0);
      dp[n-1]=a[n-1];
      for(int i=n-2;i>=0;i--){
        dp[i] = max(dp[i+1],a[i]);
      }
      stack<int> st;
      vector<int> res;
      for(int i=0;i<n;i++){
        st.push(a[i]);
        while(st.empty()==false && i<n-1 && st.top()>=dp[i+1]){
          res.push_back(st.top());
          st.pop();
        }
      }
      
      while(st.empty()==false){
        res.push_back(st.top());
        st.pop();
      }
      return res;
    }
};

C 解法, 执行用时: 10ms, 内存消耗: 1500KB, 提交时间: 2021-09-10

/**
 * 栈排序
 * @param a int整型一维数组 描述入栈顺序
 * @param aLen int a数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
void push_(int k,int * arr,int *top);
int pop_(int * arr, int * top);
int check_back(int * a, int aLen,int idx, int * arr,int top);

int* solve(int* a, int aLen, int* returnSize ) {
    // write code here
    //when no element bigger than the end of the arr; pop;      else push.
    
    int arr[aLen],top = -1;
    int *result,rtop = -1;
    result = (int *)malloc(sizeof(int)*50000);
    int i = 0;
    
    while ( rtop < aLen - 1)
    {
        if (top == -1)
        {
            push_(a[i], arr, &top);
            i++;
        }
        if (check_back(a,aLen,i,arr,top))
        {
            rtop++;
            result[rtop] = pop_(arr, &top);
        }
        else
        {
            push_(a[i],arr,&top);
            i++;
        }
        
    }
    *returnSize = aLen;
    /*
    for (i = 0; i < *returnSize;i++)
        printf("%d\t",result[i]);
    printf("\n");
    */
    
    return result;
}

int check_back(int * a, int aLen,int idx, int * arr,int top)//if there is a number after target bigger than target.
{                                        //return 0,       else  return 1;

    while (idx < aLen)
    {
        if (a[idx] > arr[top])
            return 0;
        idx++;
    }
    return 1;
}
void push_(int k,int * arr,int *top)
{
    int i = *top + 1;
    arr[i] = k;
    *top = i;
}
int pop_(int * arr, int * top)
{
    int ntop = *top;
    ntop--;
    *top = ntop;
    return arr[ntop+1];
}

C++ 解法, 执行用时: 10ms, 内存消耗: 1740KB, 提交时间: 2021-05-19

static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
/*
target = aLen
每入栈一个a[i] 标记已访问 visit[a[i]]
已访问的要么在栈内，要么已经出栈
每次需要找能出栈的最大值
*/    
    vector<int> solve(int* a, int aLen) {
        stack<int>st;
        vector<int >ans;
        vector<bool> visit(aLen+1);
        int target = aLen;
        for(int i = 0; i < aLen; ++i){
            st.push(a[i]);
            visit[a[i]] = true;
            while(target && visit[target]) --target;//未入栈的最大值
            while(!st.empty() && target <= st.top()){//出栈最大目标值
                ans.push_back(st.top());
                st.pop();
            }
        }
        while(!st.empty()){
            ans.push_back(st.top());
            st.pop();
        }
        return ans;
    }
};

详情