Q002_super2bai_solution

[super2bai]

Question_ID: Q002

Language: Java

Time Cost: 30mins

Time Complexity: O(n)

Solution

1. First...read input string
2. Then...get command
3. And...operate

My Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Q002Max {
    static int head = -1;
    static int end = -1;
    static int max=-1;
    static int[] queue = new int[4];
    static final String numRegex = "[0-9]*";

    public static void push(int i) {
        if (head == -1) {
            head++;
        }
        if(max<i){
            max=i;
        }
        if (end == queue.length - 1) {
            int[] newQueue = new int[queue.length * 2];
            System.arraycopy(queue, 0, newQueue, 0, queue.length);
            queue = newQueue;
        }
        end++;
        queue[end] = i;
        System.out.println("None");
    }

    public static void pop() {
        if (end == -1 || queue[end] == 0) {
            System.out.println(-1);
            return;
        }
        int popValue=queue[head];
        System.out.println(popValue);
        queue[head] = 0;
        if(max==popValue){
            max = queue[0];
            for (int i = 1; i < queue.length; i++) {
                if (max < queue[i]) {
                    max = queue[i];
                }
            }
        }

        if (head != end) {
            head++;
        } else {
            head = -1;
            end = -1;
            max=-1;
        }
    }

    public static void getMax() {
        if (end == -1 || queue[end] == 0) {
            System.out.println(-1);
            return;
        }

        System.out.println(max);
    }

    private static void getCommandAndValue(String inputString) {
        String[] s = inputString.split(" ");
        String command = s[0].toLowerCase();
        if (s.length != 1 && s.length != 2) {
            System.out.println("invalid input");
        }
        if ("get_max".equals(command) || "getmax".equals(command)) {
            getMax();
        } else if ("quit".equals(command) || "exit".equals(command)) {
            System.exit(0);
        } else if ("pop".equals(command)) {
            pop();
        } else {
            if (s.length != 2 || !isNumeric(s[1]) || !"push".equals(command)) {
                System.out.println("invalid input");
                return;
            }
            int value = Integer.valueOf(s[1]);
            push(value);
        }
        System.out.println("head:" + head);
        System.out.println("end:" + end);
    }

    public static boolean isNumeric(String str) {
        Pattern pattern = Pattern.compile(numRegex);
        Matcher isNum = pattern.matcher(str);
        if (!isNum.matches()) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        while (true) {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            try {
                String read = br.readLine();
                getCommandAndValue(read.trim());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}

[rbee3u]

你这种实现跟 @大菠萝 一样，只是粗鲁地实现了题意，但是 get_max 的效率还有待提升。

[super2bai]

贴一波PPPPPPPP大佬的Java版本。

    static Queue<Integer> q = new LinkedList<Integer>();
    static Deque<Integer> d = new LinkedList<Integer>();

    public static void push(int elem) {
        q.offer(elem);
        while (d.peekLast() != null && d.peekLast() < elem)
            d.pollLast();
        d.offerLast(elem);
    }

    public static int pop() {
        if (q.peek() == null)
            return -1;

        int res = q.poll();
        if (res == d.peekFirst())
            d.pollFirst();
        return res;
    }

    public static int get_max() {
        if (d.peekLast() == null)
            return -1;
        return d.peekFirst();
    }

    public static void main(String[] args) throws java.lang.Exception {
        Scanner sc = new Scanner(System.in);
        while (true) {
            String input = sc.nextLine();
            String cmd[] = input.split(" ");
            if ("push".equals(cmd[0])) {
                int arg = Integer.valueOf(cmd[1]).intValue();
                push(arg);
                System.out.println("None");
            } else if ("pop".equals(cmd[0])) {
                System.out.println(pop());
            } else if ("get_max".equals(cmd[0])) {
                System.out.println(get_max());
            }
        }
    }