Stack & queue of interview high-frequency algorithm questions

This is the 30th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The stack and queue

The full text overview

Basic knowledge of

# # # # stack

A stack is a fifo data structure. A great example of this is stacking plates. When we put the plates, we can only put them one by one from the bottom up; When you take it, you can only take it one by one from the top down, not from the middle.

A stack is a linear table with limited operations, allowing data to be processed at only one end. There are two main operations, namely, push and push, that is, insert data at the top of the stack and remove data at the top of the stack.

Stacks can be implemented as arrays or linked lists. A stack implemented in arrays is called a sequential stack, and a stack implemented in linked lists is called a chained stack.

The queue

A queue is a first-in, first-out data structure. You can think of it like waiting in line to buy a ticket. Those who come first buy first, and those who come later are only allowed to stand at the end of the line.

A queue, like a stack, is a linear table data structure with limited operation. There are two main operations: out and in, that is, take an element from the head of the team and insert an element at the end of the team.

Queues can be implemented using arrays or linked lists. Arrays are called sequential queues, and lists are called chained queues.

Implement queues with two stacks

Offer 09. Implement queues with two stacks

Problem description

Use two stacks to implement a queue, complete n times to insert integer (push) at the end of the queue and delete integer (pop) at the head of the queue. Elements in the queue are of type int. Ensure that the operation is valid, that is, ensure that there are elements in the queue when the POP operation is performed.

Example:

Input: [” PSH1 PSH2 “, “”,” POP “, “POP”]

Return values: 1,2

Description:

“PSH1” : inserts 1 into the end of the queue. “PSH2” : inserts 2 into the end of the queue. “POP” : deletes an element and returns 1

To analyze problems

First, we need to know the difference between a queue and a stack.

1. A queue is a first-in, first-out data structure. Elements in a queue enter the queue from the back end and exit from the front end. It’s like waiting in line for a ticket.
2. A stack is a lifO data structure. Elements in the stack are pushed in and ejected from the top of the stack.

To implement the fifO feature of queues with two stacks, we need a stack to reverse the order in which elements are queued.

Team entry operation Push:

Since the stack is lifO and the queue is fifO, to use the stack to implement fifO, we need to put the new element at the bottom of the stack. To do this, we need to move the elements from S1 to S2, then push the new elements into S2, and then pop all the elements from S2 again into S1. This enables the new element to be pushed to the bottom of the stack.

    def push(self, node):
        # write code here
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        self.stack2.append(node)
        while self.stack2:
            self.stack1.append(self.stack2.pop())
Copy the code

Out of line operation Pop:

We can pop it directly from S1, because after the inversion, the top element in S1 is the first element on the stack, the first element in the queue.

    def pop(self):
        if self.stack1:
            return self.stack1.pop()
Copy the code

Let’s look at the complete code implementation.

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        self.stack2.append(node)
        while self.stack2:
            self.stack1.append(self.stack2.pop())

    def pop(self):
        if self.stack1:
            return self.stack1.pop()
Copy the code

We can see that the time complexity of the enqueue operation is O(n) and the space complexity is also O(n). The queuing time complexity is O(1), and the space complexity is also O(1).

To optimize the

In the algorithm above, I don’t know if you noticed, but every time we push a new element, we need to move from S1 to S2, and then from S2 back to S1. This is obviously redundant. In fact, we only need to plug in S1 to join the team. In order to implement fifO, we need to reverse the elements of S1, since the first element is pushed at the bottom of the stack. We can Pop elements out of S1 and push S2. This puts S1 at the bottom of the stack at the top of the stack S2, and we pop it straight from S2. Once S2 is empty, all we have to do is transfer S1 to S2 again.

Let’s take a look at the code implementation.

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)

    def pop(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()
Copy the code

Valid parentheses

LeetCode 20. Valid parentheses

Problem description

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

Valid characters meet the following conditions:

• An open parenthesis must be closed with a close parenthesis of the same type.
• The left parentheses must be closed in the correct order.

Example:

Input: s = “()[]{}”

Output: true,

To analyze problems

This problem can be solved with the help of the data structure “stack”. As we iterate through the string, when we encounter an open parenthesis, we push it, and when we encounter a close parenthesis, we pull out the top elements of the stack to see if they are of the same type. If not, then s is not a valid string, and we return False. If so, continue traversing until the traversal is complete. After iterating through the string S, if the stack is empty, the string is valid. One thing to note here is that to speed up the determination of whether the left and right parentheses are of the same type, we introduce a hash table to store each type of parentheses. The keys of the hash table are close parentheses and the values are open parentheses of the same type.

Let’s take a look at the code implementation.

If len(s) % 2 == 1: return false dict = {")": "(", "]": if len(s) % 2 == 1: false dict = {")": "(", "]": [", "}": "{",} stack = list() for ch in s: Dict [ch]: return false if not stack or stack[-1]!= dict[ch]: return false if not stack or stack[-1]!= dict[ch]: return false Append (ch) # if the stack is empty, s is a valid string, otherwise it is an invalid stringCopy the code

The stack containing the min function

Refer to Offer 30. Stack containing min function

Problem description

Define the data structure of the stack, please implement a min function in this type that can get the smallest element contained in the stack, and the time complexity of calling min function, push function and pop function is O(1).

Push (value) : Pushes a value onto the stack

Pop () : Pops the top element of the stack

Top () : Gets the top element on the stack

Min () : Gets the smallest element in the stack

Example:

minStack.push(-2); --> push minstack.push (0); --> push 0 to minstack.push (-3); Minstack.min (); --> return the smallest element in the stack -- 3 minstack.pop (); Minstack.top (); Minstack.min (); Returns the smallest element in the stack -2Copy the code

To analyze problems

For a normal stack, the time complexity for push and pop is O(1) and the time complexity for min is O(N). Because we need to traverse the stack to find the minimum, we introduced a secondary stack to reduce the time complexity of min.

• Data stack A: Stack A is used to store all elements, ensuring the operation of push, pop and top.
• Secondary stack B: Stack B is used to store all elements in stack A that are not strictly decrement, that is, the minimum value in stack A is always at the top of stack B, so that the time complexity of O(1) can return the minimum value in the stack.

Let’s take a look at the code implementation.

Class Solution: def __init__(self): self.A = [] # self.B = [] # self. If not self.b or self.b [-1] >= x: self.b.append (x) def pop(self): self.a.append (x) def pop(self): self.a.append (x) def pop(self): self.a.append (x) def pop(self): If s == self.b [-1]: self.b.pop () def top(self): self.a.pop () def top(self) = self.b [-1]: self.b.pop () def top(self): Return self.A[-1] def min(self): return self.B[-1]Copy the code

Expression evaluation

Problem description

Write an integer calculator that supports addition, subtraction and multiplication and parentheses.

Example:

Enter: “(2 * (3-4))) * 5”

Return value: -10

To analyze problems

Because only supports the addition, subtraction, multiplication, brackets, so we according to the priority can be divided into three categories, namely the braces > > add, subtract, hypothesis, first remove the parentheses, then the remaining multiplication and addition and subtraction, according to the rules of operation, multiplication, and then we need to calculate the add, subtract, so we can consider, we first make a multiplication, And return these integer values after multiplication to the corresponding position of the original expression, then the value of the entire expression is equal to a series of integer plus or minus values. For the expression divided by parentheses, we can solve it recursively. The specific algorithm is as follows.

Iterate over the string S and record the operator before each number with the variable preSign, initialized to a plus sign.

1. Skip when it encounters Spaces.
2. When a number is encountered, continue iterating to find the value of the complete number and save it in num.
3. When an open parenthesis is encountered, we need to recursively evaluate the expression inside the parenthesis.
4. When the end of an operator or expression is encountered, the evaluation is determined based on the type of the previous operator.
   • If it’s a plus sign, you don’t have to evaluate it, you just push it on the stack
   • If it’s a minus sign, it takes the negative of the current number and pushes it onto the stack
   • If it’s a multiplier, pop a number from the stack and multiply the current number, then push the result onto the stack
5. Finally, sum the stack results.

Let’s take a look at the code implementation.

Class Solution: def calculate(self, s): n = len(s) # calculate(self, s): n = len(s) # calculate(self, s): n = len(s) If c=s[I] if c==' ': I = I +1 continue if C. isdigit(): num = num * 10 + ord(c) -ord ('0') # J = I +1 counts=1 # count =1 # count =1 # Num =self. Calculate (s[I +1:j-1]) I =j-1 if not c.i. digit() or I ==n-1: if preSign=="+": stack.append(num) elif preSign=="-": stack.append(-1*num) elif preSign=="*": tmp=stack.pop() stack.append(tmp*num) num=0 preSign=c i=i+1 return sum(stack) s=Solution() print(s.calculate("(3+4)*(5+(2-3))"))Copy the code

The maximum value of a sliding window

LeetCode 239. Sliding window maximum

Problem description

Given an integer array numS, there is a sliding window of size K that moves from the leftmost of the array to the rightmost of the array. You can only see k numbers in the sliding window. The sliding window moves only one bit to the right at a time. Returns the maximum value in the sliding window.

Example:

Input: [2,3,4,2,6,2,5,1], 3

Output: [4,4,6,6,6,5]

To analyze problems

The key to this problem is to find the maximum value in a sliding window. For a sliding window of size K, we can work out its maximum value by traversing, which requires O(k) time complexity. For the array NUMs of size N, there are n-k+1 Windows, so the time complexity of this algorithm is O(nk).

Through observation, we can know that for two adjacent sliding Windows, k-1 elements are shared and only one element is changed, so we can use this property to optimize our algorithm.

For the maximum problem, we can use the priority queue (big push) to solve. First, we put the first K elements of the array into the priority queue. Whenever we move to the right window, we can put a new element in the queue, the pile top element is the maximum number of all elements in the heap, but the maximum possible does not belong to the current sliding window, we need to remove the element for processing (if the maximum value is not in the current sliding window, it can only be left to the left side of the border of the sliding window, So when the slider moves to the right, the element no longer appears in the slider, so we can remove it. We keep removing the top element of the heap until it actually appears in the sliding window. At this point, the heap top element is the maximum in the sliding window.

In order to conveniently judge the position relationship between the top element of the heap and the sliding window, we can store the binary group (num, index) in the priority queue, indicating that the subscript of element NUM in the array is index.

Little was catnip: Since python only provides a small top heap, we need to invert the elements. For example, for the list [1, -3], we invert the elements and insert them into the small top heap, which looks like [-1,3]. We take the top element -1 and invert it to 1 to get the maximum value of the list 1.

Let’s take nums=[2,3,4,2,6,2,5,1] and k=3 as examples to see the specific process.

1. First of all, we put the first 3 elements of NUMS into the priority queue. The index value of the first element in the queue is 2>0, so it is added into the result. At this time, res=[4].

   

2. The next element 2 joins the queue, and the index of the first element of the queue is 2>1, which is in the window, so it is added to the result. At this time, res=[4,4].

   

3. The next element 6 joins the queue, and the index of the first element in the queue is 4>2, so it is added to the result. At this time, res=[4,4,6].

   

4. The next element 2 is added to the queue, and the index of the first element in the queue is 4>3, so it is added to the result, and then res=[4,4,6,6].

   

5. The next element 5 joins the queue, and the index of the first element is in the window, so it is added to the result, and res=[4,4,6,6,6].

   

6. The next element in queue 1, index=4<5, is not in the window, so we pop it, index= 6, is in the window, so we add it to the result, now res=[4,4,6,6,6,5].

   

The advanced

We can also solve this problem using a double-endian queue. In the process of traversing the number group, we continuously perform the operation of joining the queue to the corresponding subscripts of the elements. In the process of entering and leaving the queue, we need to ensure that the elements corresponding to the subscripts stored in the queue are sorted from large to small. Specifically, when there is a new element whose index is larger than the element at the end of the queue, we need to eject the end of the queue and repeat until the queue is empty or the new element is smaller than the element at the end of the queue.

Since the subscript elements in the queue are strictly monotonically decreasing, the element corresponding to the first subscript of the queue is the maximum in the sliding window. But the maximum may be to the left of the left edge of the sliding window, and as the window moves to the right, it will never appear in the sliding window. So we also need to keep popping elements from the head of the queue until the head of the queue element is in the window.

Let’s take nums=[2,3,4,2,6,2,5,1] and k=3. We first initialize an empty queue QUE.

1. At this point, the queue is que empty, and the subscript 0 corresponding to element 2 enters the queue. In this case, no window is formed.

   

2. At this point, queue que=[0], the element at the end of the queue is 0, which corresponds to the element in the array nums[0] < NUMs [1], so we pop 0 at the end of the queue, and the queue is empty, and we add 1 to the queue. In this case, no window is formed.

   

3. At this point, the queue que=[1], the element at the end of the queue is 1, and the element in the corresponding array is nums[1] < NUMs [2]. Therefore, we pop out the end 1 of the queue, and the queue is empty, and we add 2 to the queue. And now the first element 2 is in the window [0,2], so take out the first element.

   

4. At this point, queue que=[2], the element at the end of the queue is 2, and the element in its corresponding array is nums[2] > NUMs [3], so we add 3 to the queue. And now the first element 2 is in the window [1,3], so take out the first element.

   

5. At this point, queue que=[2,3], the element at the end of queue 3, the element in the array corresponding to it is nums[3] < NUMs [4], so we pop the end of queue 3, and the element in the array corresponding to the element at the end of queue is nums[2] < NUMs [4], so we pop the end of queue 2, and the queue is empty. We will join the team four times. And now the first element 4 is in the window [2,4], so take out the first element.

   

6. At this point, queue que=[4], the element at the end of the queue is 4, and the element in its corresponding array is nums[4] > NUMs [5], so we add 5 to the queue. And now the first element 4 is in the window [3,5], so we take out the first element.

   

7. At this point, the queue que=[4, 5], the element at the end of the queue is 5, and the element in the array corresponding to it is nums[5] < NUMs [6], so we pop the element at the end of the queue 5, and the element in the array corresponding to the element at the end of the queue is NUMs [4] > NUMs [6], so we add 6 to the queue. And now the first element 4 is in the window [4, 6], so we take out the first element.

   

8. At this point, queue que=[4,6], the element at the end of the queue is 6, and the element in the corresponding array is nums[6] > nums[7], so we add 7 to the queue. At this time, the first element 4 is not in the window [5,7], so we remove it from the queue, and the first element 6 is in the window [5,7], so we remove it.

   

Let’s take a look at the code implementation.

import collections class Solution: def maxSlidingWindow(self, nums, k): Q = collections.deque() # initialize first window for I in range(k): While q and nums[I] >= nums[q[-1]]: Q.op () # add the first element to the result ans = [nums[q[0]]] # move the window gradually to the right for I in range(k, n): While q and nums[I] >= nums[q[-1]]: Q.op () # Until the queue is empty, or smaller than the last element, q.ppend (I) # If the first element of the queue is not in the window, exit operation while q[0] <= i-k: Ans. Append (nums[q[0]]) return ans s=Solution() print(s.maaxslidingwindow ([2,3,4,2,6,2,5,1],3)Copy the code

The stack and sort

Problem description

You are given a permutation and a stack consisting of 1~ N, N numbers, and are required to be pushed in the order of the permutation. How to output the maximal lexicographic outputting sequence by using only the two operations of outputting and outputting without disturbing the order of outputting.

Permutation: Each number from 1 to N occurs only once.

Example:

Input:,4,5,3,1 [2]

Output:,4,3,2,1 [5]

To analyze problems

Since we can only use two types of operations, the first thing we want to do to maximize the lexicographical order of the unstack sequence is to make the high order as large as possible. The time we want to unstack is: if the current unstack element is larger than the next unstack element, then unstack it. When an element is removed from the stack, it is necessary to determine the size relationship between the top element and the next element to be added to the stack. If the top element is larger than the next element to be added to the stack, it is removed from the stack until the stack is empty or the condition is not satisfied.

To quickly determine if the current pushed element is greater than the one to be pushed later, we need to create an auxiliary array temp, where temp[I] represents the largest element after I. With the aid of auxiliary arrays, we can use O(1) time complexity to determine whether the current pushed element is larger than the element to be pushed later.

Let’s look at the implementation of the code.

import sys class Solution: def solve(self , a): n=len(a) res=[] if n==0: Return stack=[] temp=[0]*n temp[n-1]=-sys.maxsize-1 # fill temp # so that temp[I] represents the largest element after I for I in Range (n - 2, 1, 1) : \ [I] = Max ([I + 1], a \ [I + 1]) # iterate through group a for I in range (0, n) : if a [I] > \ [I] : Res.append (a[I]) # while stack and stack[-1] > temp[I]: res.append(stack[-1]) stack.pop() else: stack.append(a[i]) while stack: res.append(stack[-1]) stack.pop() return resCopy the code

The time complexity of this algorithm is O(n), and the space complexity is also O(n).

Monotonous stack

Problem description

Given an array arr of length n that may contain duplicate values, find the positions to the left and right of each I position that are closest to I and whose values are smaller than arr[I]. Design an algorithm that returns a two-dimensional array representing information corresponding to all locations. The position information includes: two digits L and r, if not present, the value -1, with subscripts starting at 0.

Example:

Input:,4,1,5,6,2,7 [3]

Output: [[1, 2], [0, 2], [1, 1], [2, 5], [3, 5], [2, 1], [5, 1]]

To analyze problems

The simplest solution to this problem is brute force, which is solved through a two-layer for loop. As follows:

Class Solution: def found1600mv/s (self, nums): n=len(nums) res=[] # 最 后 提 升 最 后 提 升 for I in range(0,n): For j in range(0, I): if nums[j] < nums[I]: if nums[I] < nums[I]: For j in range(n-1, I,-1): if nums[j] < nums[I]: r=j res.append([l,r]) return resCopy the code

The time complexity of this algorithm is O(n^2) and the space complexity is O(1).

Obviously, the time complexity of solving violence is too high, so how should we optimize it? In fact, this problem we can use monotone stack to solve, first let’s look at the definition of monotone stack.

Monotonous stack is refers to the elements in the stack is have the monotonicity of the stack, compared with the ordinary stack, monotonous in the stack, need to stay in the elements and stack, comparing the top element view after joining elements into the stack will destroy the monotonicity of the stack, if not, directly into the stack, or pop up until condition is satisfied.

In this case, we maintain a monotonic stack that stores array subscripts. Then iterate over the number group and do the following.

We take the position on the left of each I that is closest to I and less than ARr [I] as an example to see the execution process of the algorithm. First we go through the array from left to right.

• Let’s assume that the element traversed is arr[I], and the element in the array corresponding to top is arr[top]. Then we compare arr[I] with arr[top].
• If arr[top] > arr[I], then top is not the solution of the ith element, and it will not be the solution of any element after I (because I is closer than top and arr[I] < arr[top]), so we pop top, Until the stack is empty or the top element (the subscript of the array) corresponds to an element in the array less than arr[I].
• If arr[top] < arr[I], it means that the solution of the ith number is top, because the elements in the stack are monotonically increasing, so top is the nearest number to I, that is, top is the desired value. And then since I might be a candidate to the right of I, I can be added to the stack.

Similarly, if we traverse the array from right to left, we can find the position to the right of each I that is closest to I and less than arr[I].

Let’s look at the implementation of the code.

class Solution: def foundMonotoneStack(self , nums): N =len(nums) res=[] l=[0]*n r=[0]*n # stack=[] # stack for I in range(0,n): Num [I]> =nums[I]; num[I]> =nums[I]; num[I]> =nums[I]; Stack. Pop () l[I]=stack[-1] if stack else -1 # Stack. Append (I) stack=[] # for I in range(n-1,-1,-1): Num [I]> = nums[I]; num[I]> = nums[I]; num[I]> = nums[I]; Stack. Pop () r[I] = stack[-1] if stack else -1 # I stack. Append (I) for I in range(0,len(l)) Res.append ([l[I],r[I]]) return res s=Solution() print(s.vent ≤ 1600mv ([3,4,1,5,6,2,7])Copy the code

The time complexity of this algorithm is O(n) and the space complexity is O(n).

## Daily temperature

739. Daily temperature

Problem description

According to the daily temperature list (temperatures), calculate how many days each day we need to wait for higher temperatures. If the temperature does not rise after that point, substitute 0 at that point.

Example:

Input: Temperatures = [73,74,75,71,69,72,76,73]

Output:,1,4,2,1,1,0,0 [1]

To analyze problems

Since it requires several days to wait for higher temperatures every day, the most intuitive idea is to search backwards for each temperature value in the temperature list to find the location index of the first value that is higher than the current temperature, and then subtract the location index of the current temperature to get the desired result.

Let’s look at the implementation of the code.

class Solution(object): def dailyTemperatures(self,temperatures): N = len(temperatures) result=[0]*n # for I in range(n): if temperatures[I]<100: For j in range(I +1,n): if temperatures[j] > temperatures[I]: result[I]= J-i break return resultCopy the code

The time complexity of this algorithm is O(n^2) and the space complexity is O(n).

Obviously, the time complexity of this algorithm is too high, so do we have any optimization methods?

To optimize the

This can be optimized using a monotone stack, that is, maintaining a monotone stack of temperature indices such that the temperature values of the elements from the top of the stack to the bottom of the stack decrease successively. Specifically, we’re going through the temperature list. For each element in the temperature list [I]. If the stack is empty, I is pushed directly onto the stack; If the stack is not empty, temperatures[prev] corresponding to the element at the top of the stack are compared to the current temperature [I].

• If temperatures[Prev] < temperatures[I], the element prev at the top of the stack is removed, and the wait time for prev is i-prev. Repeat until the stack is empty or the temperature of the top element is greater than or equal to the current temperature, and then push I onto the stack.

• If temperatures[prev] > temperatures[I], element I is pushed directly.

Why can result[prev] be updated when unstack? Because the element I that is going to be dumped must correspond to temperatures[I] which are the first element to the right of [prev] to be larger than that.

Let’s look at an example of this: temperatures = 73,74,75,71,69,72,76,73.

Initially, the monotone stack is empty; Waiting days Result is [0,0,0,0,0,0,0].

Let’s look at the implementation of the code.

N = len(temperatures) # initialize a stack = [] result = [0] * n for I in range(n): Temperature = temperatures[I] # If temperatures[I] are greater than the temperatures of the elements at the top of the stack, the elements at the top of the stack are removed. while stack and temperature > temperatures[stack[-1]]: prev = stack.pop() result[prev] = i - prev stack.append(i) return resultCopy the code

The time complexity of this algorithm is O(n), and the space complexity is also O(n).