Directory
-
- Bracket matching problem
- Minimum stack
- Maximum stack
Max stack and min stack are two important variants of extreme stack. The max stack is used to store the maximum value of the current match, and the min stack is used to store the minimum value of the current match.
Bracket matching problem
Let’s take a look at the description of Likou 20 questions:
Given a string s that only includes (’, )’, {’, }’, [’, ]’, determine whether the string is valid.
A valid string must satisfy:
- The opening bracket must be closed by a closing bracket of the same type.
- Opening brackets must be closed in the correct order.
- Every right bracket has a corresponding left bracket of the same type.
Example 1:
Input: s = “()”
Output: true
Example 2:
Input: s = “()[]{}”
Output: true
Example 3:
Input: s = “(]”
Output: false
We have two solutions to this problem:
1. We use a hash table to store all symbols first, with the left symbol as key and the right symbol as value. When traversing the string, when the symbol on the left is encountered, it is pushed onto the stack. When the symbol on the right is encountered, it is compared with the symbol on the top of the stack. If there is no match, false is returned.
public boolean isValid(String s) {<!-- -->
//Get the string length
int n = s.length();
//If the string length is an odd number, return false
if (n % 2 == 1) {<!-- -->
return false;
}
//Create a HashMap to store brackets in strings
Map<Character, Character> map = new HashMap<>();
map.put('[', ']');
map.put('(', ')');
map.put('{', '}');
//Create a stack to store brackets in the string
Stack<Character> stack = new Stack<>();
//Loop through each character in the string
for (int i = 0; i < s.length(); i + + ) {<!-- -->
char item = s.charAt(i);
//If the characters in the string exist in the HashMap, push them onto the stack
if (map.containsKey(item)) {<!-- -->
stack.push(item);
} else {<!-- -->
//If the stack is not empty, pop the top element of the stack. If the popped element does not match the characters in the current string, return false
if (stack.isEmpty() == false) {<!-- -->
char pop = stack.pop();
if (map.get(pop) != item) {<!-- -->
return false;
}
} else {<!-- -->
return false;
}
}
}
//If the stack is empty, return true, otherwise return false
return stack.isEmpty();
}
- Simply use the stack. If you encounter the symbol on the left, push it directly into the stack. When you encounter the symbol on the right, you will first determine whether the stack is empty. If it is empty, it will return false. If it is not empty, the top element of the stack will be popped. If the top element of the stack does not match, The symbol on the left directly returns false, and the last element is traversed and the return stack is empty.
public boolean isValid(String s) {<!-- -->
int n = s.length();
// If the string length is an odd number, return false directly
if (n % 2 == 1) {<!-- -->
return false;
}
//Create a stack
Deque<Character> stack = new LinkedList<>();
// Traverse the string
for (int i = 0; i < s.length(); i + + ) {<!-- -->
char c = s.charAt(i);
// If the current character is a left bracket, push it onto the stack
if (c == '(' | c == '[' || c == '{') {<!-- -->
stack.push(c);
// If the current character is a right bracket, pop an element from the stack. If the popped element does not match the current character, return false
} else if (c == '}' || c == ']' || c == ')') {<!-- -->
if (stack.isEmpty()) {<!-- -->
return false;
}
char top = stack.pop();
if ((top != '(' & amp; & amp; c == ')') || (top != '{' & amp; & amp; c == '}') || (top != '[' & amp; & amp; c == ']')) {<!-- -->
return false;
}
}
}
//If the stack is empty, return true, otherwise return false
return stack.isEmpty();
}
Minimal stack
Let’s look at the description of Likou 155 question:
Design a stack that supports push, pop, and top operations and can retrieve the smallest element in constant time.
Implement the MinStack class:
- MinStack() initializes the stack object.
- void push(int val) Push element val onto the stack.
- void pop() removes the element at the top of the stack.
- int top() Gets the element at the top of the stack.
- int getMin() Gets the smallest element in the stack.
The popular understanding of this question is to provide a method for the stack to obtain the smallest element in constant time.
We can design an auxiliary stack to insert and delete synchronously with the element stack to store the minimum value of each element when it is pushed into the stack (that is to say, in the auxiliary stack, what we insert every time is the minimum value in the element stack)
- When an element is pushed onto the stack, we take the minimum value stored on the top of the current auxiliary stack and insert it into the auxiliary stack with the minimum value among the elements currently being pushed onto the stack.
- When an element is to be popped from the stack, we also pop the top element of the auxiliary stack.
Let’s look at the specific implementation code:
class MinStack {<!-- -->
//Define two double-ended queues to store the input value and the current minimum value respectively.
Deque<Integer> xStack;
Deque<Integer> minStack;
public MinStack() {<!-- -->
//Initialize the double-ended queue
xStack = new LinkedList<>();
minStack = new LinkedList<>();
//The first minimum value is set to the maximum value
minStack.push(Integer.MAX_VALUE);
}
public void push(int val) {<!-- -->
// Enter a value
xStack.push(val);
// Compare the current minimum value with the input value and take the smaller value
minStack.push(Math.min(minStack.peek(), val));
}
public void pop() {<!-- -->
// Pop the last value of the deque
xStack.pop();
minStack.pop();
}
public int top() {<!-- -->
// Return the last value of the deque
return xStack.peek();
}
public int getMin() {<!-- -->
// Return the minimum value of the deque
return minStack.peek();
}
}
Max stack
Similar to the minimum stack implementation method, find the maximum value.
What needs attention is the last method, popping the maximum value, specifically getting the maximum element, then popping all the elements above the maximum value in the digital stack and storing them in the new stack, then popping the maximum value, and finally putting them in the new stack elements are pushed back onto the number stack.
Since Likou’s maximum stack is a VIP question, we can try Niuke’s maximum stack problem.
class MaxStack {<!-- -->
//Define two stacks, one to store numbers and the other to store the maximum value
Deque<Integer> xStack;
Deque<Integer> maxStack;
public MaxStack() {<!-- -->
//Initialize two stacks
xStack = new LinkedList<>();
maxStack = new LinkedList<>();
}
public void push(int val) {<!-- -->
// Get the current maximum value. If the stack is empty, the maximum value is the current value.
int max = maxStack.isEmpty() ? val : maxStack.peek();
// Compare the current value and the maximum value and take the maximum value
max = max > val ? max : val;
//Push the value and maximum value onto the stack respectively
xStack.push(val);
maxStack.push(max);
}
public int pop() {<!-- -->
// Pop the top element of the maximum stack
maxStack.pop();
// Pop the top element of the number stack
return xStack.pop();
}
public int top() {<!-- -->
// Return the top element of the digital stack
return xStack.peek();
}
public int peekMax() {<!-- -->
//Return the top element of the maximum value stack
return maxStack.peek();
}
public int popMax() {<!-- -->
// Get the top element of the maximum value stack
int max = peekMax();
//Create a stack
Stack<Integer> stack = new Stack<>();
// When the top element of the stack is not equal to the maximum value, push the top element of the stack onto the stack
while (top() != max) {<!-- -->
stack.push(pop());
}
// Pop the top element of the digital stack
pop();
//Pop the elements from the stack and push them into the digital stack
while (!stack.isEmpty()) {<!-- -->
push(stack.pop());
}
// Return the maximum value
return max;
}
}