232. Implement queue with stack (simple)

Use the stack to implement the following operations of the queue:

• push(x) -- put an element at the end of the queue.
• pop() -- removes the element from the queue header.
• peek() -- returns the element at the head of the queue.
• empty() -- returns whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // Return 1
queue.pop();   // Return 1
queue.empty(); // Return false

explain:

• You can only use standard stack operations -- that is, only push to top, peek/pop from top, size, and is empty operations are legal.
• Your language may not support stacks. You can use list or deque (double ended queue) to simulate a stack, as long as it is a standard stack operation.
• It is assumed that all operations are valid (for example, an empty queue will not call pop or peek operations).

answer:
Two stack structures are used: push and pop

• Join the team: enter the push stack
• Out of the team:
  If pop is empty, the number in push stack will be poured into pop in turn, and pop will pop up at the top of pop stack
  If pop is not empty, pop will pop up at the top of pop stack

JAVA code:

class MyQueue {
    private Stack<Integer> push;
    private Stack<Integer> pop;

    /** Initialize your data structure here. */
    public MyQueue() {
        push = new Stack<Integer>();
        pop = new Stack<Integer>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        push.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (pop.empty()){
            while (!push.empty()){
                pop.push(push.pop());
            }
        }
        return pop.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if (pop.empty()){
            while (!push.empty()){
                pop.push(push.pop());
            }
        }
        return pop.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        if (push.empty() && pop.empty()){
            return true;
        }
        else return false;
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

• Join the team

Time complexity: O(1)
Space complexity: O(n)

• Out of the team

Amortization time complexity: O(1)
Space complexity: O (1)

225. Implement stack with queue (simple)

Use queue to realize the following operations of stack:

• push(x) -- push element x onto the stack.
• pop() -- delete the element at the top of the stack.
• top() -- get the stack top element.
• empty() -- returns whether the stack is empty

be careful:

• You can only use the basic operations of the queue -- that is, push to back, peek/pop from front, size, and is empty. These operations are legal.
• Your language may not support queues. You can use list or deque to simulate a queue, as long as it is a standard queue operation.
• You can assume that all operations are valid (for example, pop or top operations will not be called for an empty stack).

Solution:
The stack structure is implemented with two queues.
Queue: first in first out
Stack: first in, last out
Two queues are used: data and help

Out of stack:

1. Divide the last number in data, and the remainder will be put into the queue in turn.
2. The only one in the data is counted out of the queue
3. data and help address exchange

Stack: directly enter the queue data

JAVA code:

class MyStack {
    private Queue<Integer> data;
    private Queue<Integer> help;
    /** Initialize your data structure here. */
    public MyStack() {
        data = new LinkedList<Integer>();
        help = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        data.add(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        while (data.size()>1){
            help.add(data.remove());
        }
        int top = data.remove();
        Queue<Integer> temp = data;
        data = help;
        help = temp;
        return top;
    }
    
    /** Get the top element. */
    public int top() {
        while (data.size()>1){
            help.add(data.remove());
        }
        int top = data.peek();
        help.add(data.remove());
        Queue<Integer> temp = data;
        data = help;
        help = temp;
        return top;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        if (data.isEmpty()){
            return true;
        }
        else return false;
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

Time complexity: in team O(1), out of team O(n)

155. Minimum stack (simple)

Design a stack that supports push, pop and top operations and can retrieve the smallest element in a constant time.

• push(x) -- push element x onto the stack.
• pop() -- delete the element at the top of the stack.
• top() -- get the stack top element.
• getMin() -- retrieves the smallest element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> return -3.
minStack.pop();
minStack.top();      --> Return 0.
minStack.getMin();   --> return -2.

answer:
Design two stacks: data and min
data represents the current stack, and min saves the smallest element of the current stack.

When entering the stack: compare the current element x with min and the top element at the top of the stack

1. If x < top, then x enters the min stack at the same time
2. If x > = top, the value top is put into the min stack

When leaving the stack: data and min pop up the top elements of the stack at the same time.

The top element of mini is the smallest element in the data stack.

JAVA code

class MinStack {
    /** initialize your data structure here. */
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;

    public MinStack() {
        stackData = new Stack<Integer>();
        stackMin = new Stack<Integer>();
    }

    public void push(int x) {
        stackData.push(x);
        if (!stackMin.isEmpty()) {
            if (x < stackMin.peek()) {
                stackMin.push(x);
            }
            else stackMin.push(stackMin.peek());
        }
        else{
            stackMin.push(x);
        }
    }

    public void pop() {
        stackData.pop();

        stackMin.pop();

    }

    public int top() {
        return stackData.peek();
    }

    public int getMin() {
        return stackMin.peek();
    }
}

Time complexity: O(1)
Space complexity: O(n)

20. Valid brackets (simple)

Given a string that only includes' (',' ',' {','} ',' [','] ', judge whether the string is valid.
Valid strings must meet:
The left parenthesis must be closed with the same type of right parenthesis.
The left parentheses must be closed in the correct order.
Note that an empty string can be considered a valid string.

Example 1:

input: "()"
output: true

Example 2:

input: "()[]{}"
output: true

Example 3:

input: "(]"
output: false

Example 4:

input: "([)]"
output: false

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<s.length(); i++){
            if (!stack.isEmpty() && ((stack.peek() == '('&& s.charAt(i)==')')||(stack.peek() == '{'&& s.charAt(i)=='}')||(stack.peek() == '['&& s.charAt(i)==']')))
            stack.pop();
            else stack.push(s.charAt(i));
        }
        return stack.isEmpty()? true: false;
    }
}

Time complexity O(n)
Spatial complexity O(n)

739. Daily temperature * (medium)

According to the daily temperature list, please regenerate a list. The output of the corresponding position is how long it needs to wait before the temperature rises beyond the number of days of that day. If it will not rise later, please replace it with 0 in this position.

For example, given a list 
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，
Your output should be [1, 1, 4, 2, 1, 1, 0, 0]. 

Tip: the range of temperature list length is [1, 30000]. The value of each temperature is Fahrenheit, which is an integer in the range of [30, 100].

Solution:
1. Violence Act
Each element looks back for the subscript of the first number larger than it

//Violent algorithm
// Each element looks back for a number larger than it
class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];
        for(int i = 0; i<T.length; i++){
            for (int j = i; j<T.length; j++){
                if (T[j]>T[i]){
                    res[i] = j-i;
                    break;
                }
            }
        }
        return res;
    }
}

Time complexity O(n^2)
Spatial complexity O(n), save results

2. Use a next array to store the subscript of each element*
Traverse the element from back to front, and find the element whose subscript is larger than the current element in the next. The element with the smallest value in the next is the element closest to the current element.

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] next = new int[101];
        Arrays.fill(next, Integer.MAX_VALUE);
        int[] res = new int[T.length];
        for (int i=T.length-1; i>=0; i--){
            int curr = Integer.MAX_VALUE;   //In next, the current element value, that is, the subscript of the element larger than T[i]
            //Find the element larger than the current element and closest to the current element in the next array to get its subscript
            for (int j = T[i]+1; j<101; j++){
                if (next[j] < curr){
                    curr = next[j];  
                }
            }
            if (curr<Integer.MAX_VALUE)
                res[i] = curr-i;
            next[T[i]] = i;
        }
        return res;
    }
}

Time complexity O(nw), w is the width of the range of element values
Spatial complexity O(n+w)

3. Use stack*
Store element subscripts in the stack.
Traverse the array in reverse order. If the current element is larger than the element corresponding to the subscript in the stack, exit the stack until the current element is smaller than the element corresponding to the subscript in the stack. Then the subscript to be found is in the stack.

//Stack
class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = T.length-1; i>=0; i--){
            while (!stack.isEmpty() && T[i]>=T[stack.peek()]){
                stack.pop();
            }
            if (!stack.isEmpty())
                res[i] = stack.peek()-i;
            stack.push(i);
        }
        return res;
    }
}

Time complexity O(n)
Spatial complexity O(n)

503. Next larger element II

Given a circular array (the next element of the last element is the first element of the array), the next larger element of each element is output. The next larger element of the number x is in the array traversal order, and the first number after this number is larger than it, which means that you should cycle through its next larger number. If not, output - 1.

Example 1:

input: [1,2,1]
output: [2,-1,2]
explain: The next larger number of the first 1 is 2;
The number 2 cannot find the next larger number; 
The next maximum number of the second 1 needs a circular search, and the result is also 2.

Note: the length of the input array will not exceed 10000.

Solution: using stack
Similar to question 739, the difference is that the array given in this question is a circular array.
Access to circular arrays can be in the following form: I% nums Length, I is any number.
For this problem, we only need to access the array twice, so the value of i is 0 ~ 2 * num length-1
It can be understood as each number in the array. I hope I can access the number behind it and the number in front of it.

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int size = nums.length;
        int[] res = new int[size];
        Stack<Integer> stack = new Stack<>();
        for (int i = 2*size-1; i>=0; i--){      
            while (!stack.isEmpty() && nums[i%size] >= nums[stack.peek()]){
                stack.pop();
            }
            res[i%size] = stack.isEmpty()? -1: nums[stack.peek()];
            stack.push(i%size);
        }
        return res;
    }
}

Time complexity O(n)
Spatial complexity O(n)