题解 | #和为K的连续子数组#

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> rec(aLen, 0);
        rec[aLen-1] = a[aLen-1];
        
        for(int i=aLen-2; i>=0; i--){
            rec[i] = max(rec[i+1], a[i]);
        }
        
        vector<int> res;
        stack<int> stk;
        
        for(int i=0; i<aLen; i++){
            stk.push(a[i]);
            while(!stk.empty() && i<aLen-1 && stk.top() > rec[i+1]){
                res.push_back(stk.top());
                stk.pop();
            }
        }
        
        while(!stk.empty()){
            res.push_back(stk.top());
            stk.pop();
        }
        
        return res;
    }
};