Sword finger Offer 09 Queue with two stacks

subject
Implement a queue with two stacks. The declaration of the queue is as follows. Please implement its two functions appendTail and deleteHead to insert integers at the end of the queue and delete integers at the head of the queue respectively. (if there are no elements in the queue, the deleteHead operation returns - 1)

Example 1:

Input:
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
Output: [null,null,3,-1]
Example 2:

Input:
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
Output: [null,-1,null,null,5,2]
Tips:

1 <= values <= 10000
At most 10000 calls will be made to appendTail and deleteHead

Source: LeetCode
Link: https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
analysis
Let's first analyze the queue and stack operation by matching the bottom of the stack with the head of the team, and the top of the stack with the tail of the team. In this case, joining the team can be regarded as entering the stack, and the difficulty lies in leaving the team.

The result of the out of queue operation is to take out the first element of the queue, which corresponds to taking out the element at the bottom of the stack. To take out the elements at the bottom of the stack, first take other elements out of the stack, press the elements out of the stack into another stack, take out the elements at the bottom of the stack, and then put these elements back.
code

typedef struct {
    int *values;
    int top;
    int maxlength;
} CQueue;

int step = 10;

CQueue* cQueueCreate() {
    CQueue* obj;
    obj = (CQueue *)malloc(sizeof(CQueue));
    obj->values=(int *)malloc(step * sizeof(int));
    obj->top=-1;
    obj->maxlength=0;
    return obj;
}

int pop(CQueue* obj){
    int values = obj->values[obj->top--];
    return values;
}

void push(CQueue* obj, int value){
    if(obj->top+2 > obj->maxlength){
        obj->maxlength+=step;
        obj->values = (int *)realloc(obj->values, obj->maxlength * sizeof(int));
    }
    obj->values[++obj->top]=value;
}

int getlength(CQueue* obj){
    return obj->top+1;
}

void cQueueAppendTail(CQueue* obj, int value) {
    push(obj, value);
}

int cQueueDeleteHead(CQueue* obj) {
    if(getlength(obj)==0){
        return -1;
    }
    CQueue* tmp = cQueueCreate();
    while(getlength(obj)>1){
        int v = pop(obj);
        push(tmp, v);
    }
    int headvalue = pop(obj);
    while(getlength(tmp)){
        int v = pop(tmp);
        push(obj, v);
    }
    free(tmp->values);
    free(tmp);
    return headvalue;
}

void cQueueFree(CQueue* obj) {
    free(obj->values);
    free(obj);
}

/**
 * Your CQueue struct will be instantiated and called as such:
 * CQueue* obj = cQueueCreate();
 * cQueueAppendTail(obj, value);
 
 * int param_2 = cQueueDeleteHead(obj);
 
 * cQueueFree(obj);
*/

Sword finger Offer 30 Stack containing min function

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

Example:

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

Tips:

The total number of calls of each function shall not exceed 20000

Source: LeetCode
Link: https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
analysis
The time complexity is required to be O(1), and the operation in and out time of the stack is also O(1), that is, to store the maximum and minimum values synchronously when the data is in the stack, we should focus on the in and out of the stack. Here we define a new minvalues array as the minimum stack. When an element is put into the stack, if the previous stack is empty, it is obvious that this element is the minimum value. When the stack is not empty, if the current element is less than the value of the smallest stack, the value of this element will be synchronously pressed to the smallest stack. Otherwise, the smallest stack (stack top element) of the smallest stack will be pressed to the top of the smallest stack. The stack and the minimum stack can be synchronized into and out of the stack to ensure that the top element of the minimum stack is the minimum value
code

typedef struct {
    int* values;
    int* minvalues;
    int top;
    int maxlength;
} MinStack;

/** initialize your data structure here. */
int step=100;

MinStack* minStackCreate() {
    MinStack* obj;
    obj = (MinStack *)malloc(sizeof(MinStack));
    obj->values = (int *)malloc(10000 * sizeof(int));
    obj->minvalues = (int *)malloc(10000 * sizeof(int));
    obj->top = -1;
    obj->maxlength = 10000;
    return obj;
}

void minStackPush(MinStack* obj, int x) {
    if(obj->top+2 > obj->maxlength){
        obj->maxlength += step;
        obj->values = (int *)realloc(obj->values, obj->maxlength*sizeof(int));
        obj->minvalues = (int *)realloc(obj->minvalues, obj->maxlength*sizeof(int));
    }
    if((obj->top == -1) || (x < minStackMin(obj))){
        obj->minvalues[obj->top+1] = x;
    }else{
        obj->minvalues[obj->top+1] = minStackMin(obj);
    }
    obj->values[++obj->top]=x;
}

void minStackPop(MinStack* obj) {
    obj->top--;
}

int minStackTop(MinStack* obj) {
    return obj->values[obj->top];
}

int minStackMin(MinStack* obj) {
    return obj->minvalues[obj->top];
}

void minStackFree(MinStack* obj) {
    free(obj->values);
    free(obj->minvalues);
    free(obj);
}

/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, x);
 
 * minStackPop(obj);
 
 * int param_3 = minStackTop(obj);
 
 * int param_4 = minStackMin(obj);
 
 * minStackFree(obj);
*/

Sword finger Offer 59 - I. maximum value of sliding window

Given an array num and the size k of the sliding window, please find the maximum value in all sliding windows.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]

Explanation:

Position of sliding window	Maximum
[1 3 -1] -3 5 3 6 7	3
1 [3 -1 -3] 5 3 6 7	3
1 3 [-1 -3 5] 3 6 7	5
1 3 -1 [-3 5 3] 6 7	5
1 3 -1 -3 [5 3 6] 7	6
1 3 -1 -3 5 [3 6 7]	7

Tips:

• You can assume that k is always valid. When the input array is not empty, 1 ≤ k ≤ the size of the input array.

analysis
We can use the double ended queue to maintain a monotonic non decreasing queue to represent the current maximum value. Because the queue is monotonic and non decreasing, the element at the head of the queue is the minimum element. Please refer to the next question for detailed analysis
code

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> dq; 
        if(nums.size()==0||k==0){
            return ans;
        }
        for(int i=0; i < k; i++){
            while(!dq.empty() && nums[dq.back()] <= nums[i]){
                dq.pop_back();
            }
            dq.push_back(i);
        }
        ans.push_back(nums[dq.front()]);
        for(int i=k; i < nums.size(); i++){
            while(!dq.empty() && nums[dq.back()] <= nums[i]){
                dq.pop_back();
            }
            dq.push_back(i);
            while(dq.front() <= i - k){
                dq.pop_front();
            }
            ans.push_back(nums[dq.front()]);
        }
        return ans;
    }
};

Sword finger Offer 59 - II Maximum number of queues

Please define a queue and implement the function max_value gets the maximum value in the queue and requires the function max_value,push_back and pop_ The average sharing time complexity of front is O(1).

If the queue is empty, pop_front and max_value needs to return - 1

Example 1:

Input:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
Output: [null,null,null,2,1,2]

Example 2:

Input:

["MaxQueue","pop_front","max_value"]
[[],[],[]]
Output: [null,-1,-1]

Restrictions:

1 <= push_ back,pop_ front,max_ Total operands of value < = 10000
1 <= value <= 10^5

analysis
In the process of entering the queue, the two-way queue should enter the queue from the back. At this time, if there is an element smaller than the current element in the front, it will not affect the maximum value of the queue, so you can leave the queue directly. When the queue is dequeued, if the dequeued element happens to be the first element in the two-way queue, it indicates that the current maximum element has been dequeued. At this time, the first element of the two-way queue should be dequeued
code

class MaxQueue {
public:
    MaxQueue() {

    }
    queue<int> q;
    deque<int> dq;
    int max_value() {
        if(dq.empty()){
            return -1;
        }
        return dq.front();
    }
    
    void push_back(int value) {
        q.push(value);
        while(!dq.empty() && dq.back() < value){
            dq.pop_back();
        }
        dq.push_back(value);
    }
    
    int pop_front() {
        if(q.empty()){
            return -1;
        }
        int value = q.front();
        if(dq.front() == value){
            dq.pop_front();
        }
        q.pop();
        return value;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */