题解 | #栈和排序#

1. 记录未入栈且未遍历到的元素的最大值（max初始为n）
2. 从数组中找到max以后将其放入结果集，并将最大数max减1

遍历过程中会出现三种情况：1.max已经在栈中，且为栈顶元素 2.max已经在栈中，且不为栈顶元素 3.max不在栈中 针对情况1：直接将栈顶元素出栈放入结果集 针对情况2:修改最大值，将最大值减1，跳回步骤1 针对情况3:继续遍历，直到找到max 遍历完整个数组后：将栈中元素依次弹出放入结果集。

public int[] solve (int[] a) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int n = a.length;
        int[] ans = new int[n];
        int k = 0;//记录结果集元素插入的当前下标
        int max = n;//记录剩余待扫描元素的最大值，初始为n
        for(int i = 0; i < n; i++) {
            if(Math.abs(a[i]) == max) {
            //当前元素为剩余元素（包含当前元素）的最大值，则直接加入结果集，并将max修改成下一个待寻找的max值
                ans[k++] = Math.abs(a[i]);
                --max;
            }else if(Math.abs(a[i]) < max){
            //当前元素不是要寻找的那个最大值，则将其入栈并做已入栈标记，即将其值对应下标位置的元素值取反
                stack.push(Math.abs(a[i]));
                a[Math.abs(a[i])-1] *= -1;
            }
            while(true) {
                if(!stack.isEmpty() && stack.peek() == max) {
                //情况1：如果栈顶元素就是要找的最大值，则将其出栈放入结果集，并将max修改成下一个待寻找的max值
                    ans[k++] = stack.pop();
                    --max;
                }else if(max > 0 && a[max-1] < 0){
                //情况2：如果最大值已经入栈，且不是栈顶元素，则直接将max修改成下一个待寻找的max值
                    --max;
                }else{
                //情况3：如果最大值不在栈中或者栈为空或者max=0（即所有元素均遍历），则退出while循环，继续for循环
                    break;
                } 
               //此处之所以用while循环，是因为其中情况1和情况2对max做了修改，需要再一次进行判断
            }
        }
        while(!stack.isEmpty()) {
        //若栈不空，依次将栈中元素弹出放入结果集。
            ans[k++] = stack.pop();
        }
        return ans;
    }