栈和排序 题解

这道题就是贪心思路 遇到最大值就出栈输出即可。
将输入的数值存在两个数组a和数组b当中，将b排序。
用visit数组作为没有进栈或者输出的数字。
用p作为指针指向剩余没有进栈以及输出元素的最大值
如果a[i]正好是最大值就直接输出，并将其标记。然后修改p的值使其指向剩余元素的最大值。
如果栈顶元素大于等于剩余元素最大值的话 就出栈输出。
否则直接进栈，并将其标记。
最后把栈中元素输出即可。

import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
    public static void main(String args[])throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int n = (int)in.nval;
        int a[] = new int[n+1];
        int b[] = new int[n+1];
        boolean visit[] = new boolean[n+1];
        for(int i=1;i<=n;i++)
        {
            in.nextToken();
            a[i] = (int)in.nval;
            b[i] = a[i];
        }
        Arrays.sort(b);
        int p=n;
        Stack<Integer>stack = new Stack<>();
        for(int i=1;i<=n;i++)
        {
            if(a[i]==b[p])
            {
                out.print(a[i]+" ");
                visit[a[i]] = true;
                p--;
                while(visit[b[p]]==true)
                    p--;
                while(stack.size()!=0&&stack.peek()>=b[p])
                {
                     out.print(stack.pop()+" ");
                }
            } 
            else{
                stack.add(a[i]);
                visit[a[i]] = true;
            }
        }
        while(stack.size()!=0)
        {
            out.print(stack.pop()+" ");
        }
        out.flush();
    }
                  }