Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The push and pop sequence of the stack

The title

Enter two sequences of integers. The first sequence represents the push order of the stack. Determine whether the second sequence is the eject order of the stack. Assume that all the numbers pushed are not equal. For example, the sequence {1,2,3,4,5} is a pushdown sequence of a stack, and the sequence {4,5,3,2,1} is a corresponding pop-up sequence of the pushdown sequence, but {4,3,5,1,2} cannot be a pushdown sequence of the pushdown sequence.

Source: LeetCode

Train of thought

The process of pushing and pushing was simulated with the elements in the pushed. In the process of pushing, if the top of the stack matched with the corresponding element in the popped (an I pointer was used to record the matched position), the stack should be empty at the end if the sequence was satisfied

code

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for (int num : pushed) {
            stack.push(num);
            while (!stack.isEmpty() && stack.peek() == popped[i]) {
                stack.pop();
                i++;
            }

        }
        returnstack.isEmpty(); }}Copy the code

Maximum queue size

The title

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

Source: LeetCode

Train of thought

If max.peeklast () is less than value, it should always be ejected from the queue. This is because the value of max.peeklast () is later than the value of value, and peekFirst is done from the queue head. So pop up any value less than value.

code

class MaxQueue {
    LinkedList<Integer> keep = new LinkedList<>();
    LinkedList<Integer> max = new LinkedList<>();

    public MaxQueue(a) {}public int max_value(a) {
        if (max.isEmpty()) return -1;
        return max.peekFirst();
    }

    public void push_back(int value) {
        while(! max.isEmpty() && max.peekLast() < value) { max.pollLast(); } max.offerLast(value); keep.offerLast(value); }public int pop_front(a) {
        if (keep.isEmpty()) return -1;
        int pollFist = keep.pollFirst();
        if (max.peekFirst() == pollFist) {
            max.pollFirst();
        }
        returnpollFist; }}Copy the code