“This is the 16th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

describe

  • Define a queue and implement the max_value function to get the maximum value in the queue, requiring the amortized time complexity of max_value, push_back, and pop_front to be O(1).

    If the queue is empty, pop_front and max_value must return -1

  • Example 1:
Input: [" MaxQueue ", "push_back push_back", "max_value", "pop_front", "max_value"] [[], [1], [2], [], [], []] output: 2,1,2] [null, null, null,Copy the code
  • Example 2:
Input: [" MaxQueue pop_front ", ""," max_value "] [[], [], []] output: (null, 1, 1)Copy the code
  • prompt
1 <= push_back,pop_front,max_value total operand <= 10000 1 <= value <= 10^5Copy the code

parsing

Max_value (max_value), push_back (POP_front), and push_back (POP_front) are all O(1).

If the amortized complexity is not O(1), you can use one queue direct violent solution, but if the amortized complexity is one violent solution, the time is too long. So we do it with two columns, and the first column is the normal operation that implements push_back and pop_front, and they have one amortized complexity.

The key is the max_value method and that’s where our second pair of columns comes in and we can write logic so that the largest element in the first queue is always first or last, and then we can use the queue implementation class method to get the maximum, According to the specific analysis, the amortization complexity of the second queue is O(constant) when the specific logic is implemented and when the queuing operation is performed, so its amortization complexity is O(1), and that of pop_front is also O(1), so it is in line with the question.

The sample

class MaxQueue { private LinkedList<Integer> queue; private LinkedList<Integer> LinkedList; Public MaxQueue() {queue = new LinkedList<>(); LinkedList = new LinkedList<>(); } public int max_value() { if (LinkedList.isEmpty()){ return -1; } return LinkedList.peekFirst(); } public void push_back(int value) { queue.addLast(value); while (! LinkedList.isEmpty()&&value>LinkedList.peekLast()){ LinkedList.removeLast(); } LinkedList.offer(value); } public int pop_front() { if (queue.isEmpty()){ return -1; } int result= queue.pollFirst(); if (result==LinkedList.peekFirst()){ LinkedList.pollFirst(); } return result; } } /** * Your MaxQueue object will be instantiated and called as such: * MaxQueue obj = new MaxQueue(); * int param_1 = obj.max_value(); * obj.push_back(value); * int param_3 = obj.pop_front(); * /Copy the code

Running results:

Result: Yes

Execution time: 31 ms, beating 77.55% of all Java commits

Memory consumption: 46.2 MB, beating 65.39% of all Java commits