Stacks and queues and priority queues

1. Push in and pop-up sequence of stack

Enter two integer sequences. The first sequence represents the push in order of the stack. Please judge whether the second sequence may be the pop-up order of the stack. Assume that all the numbers pushed into the stack are not equal. For example, sequence 1,2,3,4,5 is the pressing sequence of a stack, and sequence 4,5,3,2,1 is a pop-up sequence corresponding to the pressing sequence, but 4,3,5,1,2 cannot be the pop-up sequence of the pressing sequence. (Note: the length of these two sequences is equal)

Idea:

• push each number in the pushed queue to the stack, and check whether this number is the next pop value in the popped sequence. If so, pop it out.

Finally, check that not all the pop values are pop values. Time complexity O(n), space complexity O(n)

class Solution {
public:
    bool validateStackSequences(vector<int>& pushV, vector<int>& popV) {
        if (pushV.empty() || popV.empty() || pushV.size() != popV.size())
            return true;
        std::stack<int> QQ;
        int index = 0;
        // Traversing the push sequence
        for (const auto &it : pushV)
        {
            QQ.push(it);
            //The stack is not empty, and the array subscript does not exceed the limit (if it is not equal, continue to push the numbers of the push sequence into the stack)
            while (!QQ.empty() && index < pushV.size() && QQ.top() == popV[index])
            {
                QQ.pop();
                index++;
            }
        }
        return index == pushV.size();
    }
};

2. Returns the maximum value in the sliding window

https://leetcode-cn.com/problems/sliding-window-maximum/

Solution 1:

Using the priority queue, maintain a large top heap of k elements (a complete binary tree is used in Java).

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0 || nums.length <= 0) {
            return null;
        }
        // To create a large top heap, you need to customize the comparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < k; i++) {
            priorityQueue.add(nums[i]);
        }
        int[] result = new int[nums.length - k + 1];
        result[0] = priorityQueue.peek();
        // Elements to be removed in each round (the leftmost element of the sliding window, note that it is num [0], not the first element of the queue)
        int last = nums[0];
        for (int i = k; i < nums.length; i++) {
            // Remove elements outside the sliding window
            priorityQueue.remove(last);
            // Add new element
            priorityQueue.add(nums[i]);
            // Take the largest first element of the priority queue
            result[i - k + 1] = priorityQueue.peek();
            // Record the elements to be removed in each round (the leftmost element of the sliding window)
            last = nums[i - k + 1];
        }
        return result;
    }
}

• Time complexity: O(nlogn), where nn is the length of the array \ textit{nums}nums. In the worst case, if the elements in the array \ textit{nums}nums increase monotonically, all elements are included in the final priority queue, and no elements are removed. Since the time complexity of putting an element into the priority queue is O(\log n)O(logn), the total time complexity is O(n \log n)O(nlogn).
• Space complexity: O(n)O(n), that is, the space required by the priority queue. All spatial complexity analysis here does not consider the O(n)O(n) space required by the returned answer, and only calculates the use of additional space.

Solution 2:

Use a double ended queue

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0 || nums.length <= 0) {
            return null;
        }
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; i++) {
            // The bidirectional queue saves the array position of the maximum value of the current window, and ensures that the value of the array position in the queue is sorted from large to small
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            //Array subscript: put at the end of the double ended queue
            deque.offerLast(i);
        }
        int[] result = new int[nums.length - k + 1];
        // Get the largest first element of the queue
        result[0] = nums[deque.peekFirst()];
        for (int i = k; i < nums.length; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            result[i - k + 1] = nums[deque.peekFirst()];
        }
        return result;
    }
}

• Time complexity: O(n)O(n), where nn is the length of the array \ textit{nums}nums. Each subscript is put into the queue exactly once and ejected from the queue at most once, so the time complexity is O(n)O(n).

• Space complexity: O(k)O(k). Different from method 1, the data structure we use in method 2 is bidirectional, so "constantly ejecting elements from the head of the queue" ensures that there will be no more than k+1k+1 elements in the queue, so the space used by the queue is O(k)O(k).

3. Return the K-th largest element in the data stream

703. The K-th largest element in the data stream

Idea:

class KthLargest {
    PriorityQueue<Integer> pq;
    final int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        pq = new PriorityQueue<Integer>();
        for (int x : nums) {
            add(x);
        }
    }

    public int add(int val) {
	    //If it is not the smallest heap of K, add it first and return directly to the top of the heap
        if (pq.size() < k) {
            pq.add(val);
        }
        // Now it is definitely the smallest heap of K, so it can be judged logically
        else if(val > pq.peek()){
            pq.poll();
            pq.add(val);
        }
        return pq.peek();
    }
}

• Time complexity: O(n*log(k))
• Space complexity: O(k)