Draw a monotonic stack for solving data structure problems

Monotone stack

First question

The implementation class is typedef and implements this class with array or int or other classes

typedef struct {
  int stack[10000];
  int stacktop;
  int minstack[10000];
  int minstacktop;  

}MinStack;//Auxiliary stack, the minimum value of stack top storage;


MinStack* minStackCreate() 
{
    MinStack* newStack      = (MinStack *) malloc(sizeof(MinStack));
    newStack->stacktop      = 0;
    newStack->minstacktop   = 0;
    return newStack;
}

void minStackPush(MinStack* obj, int val) {
obj->stack[obj->stacktop++]=val;
if(obj->minstacktop==0||obj->minstack[obj->minstacktop-1]>=val)
{
    obj->minstack[obj->minstacktop++]=val;
}
}

void minStackPop(MinStack* obj) {
if(obj->minstack[obj->minstacktop-1]==obj->stack[obj->stacktop-1])
{
    obj->minstacktop--;
}
obj->stacktop--;
}

int minStackTop(MinStack* obj) {
return obj->stack[obj->stacktop-1];
}

int minStackGetMin(MinStack* obj) {
return obj->minstack[obj->minstacktop-1];
}

void minStackFree(MinStack* obj) {
free(obj);
}//obj is a class that represents stack and auxiliary stack

Knowledge points:

1. Use an auxiliary stack to find the minimum value, and update the top of the minimum stack (minimum value) in real time when push ing and pop

2.struct definition

typedef struct{



}minstack

Second question

Using the idea of monotonic stack, the elements (subscripts) in the stack decrease monotonically. The subscripts of the elements in the stack are the subscripts that are not paired successfully. Move forward. Compared with the elements in the stack, remove the elements at the top of the stack if they are greater than, and continue to repeat the operation until the stack is empty or the traversed elements are smaller than the elements in the stack (because the stack decreases monotonically), and then move the traversed elements into the stack,

The last elements in the stack are all 0 in the last ret array, because no match was found.

int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize){
int stack[100001];
int top=0;
int *ret=(int*)malloc(sizeof(int)*temperaturesSize);
memset(ret, 0, sizeof(int) * temperaturesSize);
for(int i=0;i<temperaturesSize;i++)
{
    while(top!=0&&temperatures[i]>temperatures[stack[top-1]])
    {
int temp=stack[--top];
ret[temp]=i-temp;
    }
    stack[top++]=i;
}
*returnSize=temperaturesSize;
return ret;
}

Remember that the stack is -- top and the stack is [top + +]
 

Stack simulation queue

First question

First use the linear table to realize the stack

typedef struct{
    int*stack;
    int stkcapicity;
    int top;
}Stack;
Stack* stackcreate(int capicity)
{
    Stack*ret=(Stack*)malloc(sizeof(Stack));//Apply for space for creating a stack class
    ret->stkcapicity=capicity;
    ret->top=0;
    return ret;
}
void stackpush(Stack*obj,int x)
{
obj->stk[obj->top++]=x;
}
void stacktop(Stack*obj)
{
    return obj->stk[obj->top-1];
}
bool stackempty(Stack*obj)
{
    return obj->top==0;
}
void free(Stack*obj)
{
    free(obj->stk);
}
MyStack*ret=malloc(sizeof(MyStack));

Note that this should be written when applying for space

typedef struct{
    // Stack
    int *stack;
    // Number of elements in stack
    int stackSize;
    // Stack capacity
    int stackCapacity;
}MyStack;
MyStack* myStackCreate(int capacity){
    // Allocate memory space
    MyStack * myStack=malloc(sizeof(MyStack));
    myStack->stack=malloc(sizeof(int)*capacity);
    // There are currently no elements
    myStack->stackSize=0;
    // Stack capacity
    myStack->stackCapacity=capacity;
    return myStack;
}
void mystackpush(MyStack*mystack,int val)
{
    mystack->stack[mystack->stackSize++]=val;
}
void mystackpop(MyStack*mystack)
{
    mystack->stackSize--;
}
int mystackpeek(MyStack*mystack)
{
    return mystack->stack[mystack->stackSize-1];
}//Get stack top element
bool mystackempty(MyStack*mystack)
{
    return mystack->stackSize==0;
}
void mystackfree(MyStack*mystack)
{
    free(mystack->stack);
}

Implement queue with stack

typedef struct {
MyStack*instack;//Input stack, and all push will go in
MyStack*outstack;//Queue with two stacks
} MyQueue;


MyQueue* myQueueCreate() {
MyQueue*ret=malloc(sizeof(MyQueue));
ret->instack=myStackCreate(100);
ret->outstack=myStackCreate(100);
return ret;
}//Apply for space for class and initialize class

void myQueuePush(MyQueue* obj, int x) {
mystackpush(obj->instack,x);
}
void in2out(MyQueue*obj)
{
while(!mystackempty(obj->instack))
{
mystackpush(obj->outstack,mystackpeek(obj->instack));
mystackpop(obj->instack);
}
}//Put all instack's into outstack
int myQueuePop(MyQueue* obj) {
if(mystackempty(obj->outstack))
{
    in2out(obj);//When outstack is empty, press the of instack into it
}
int x=mystackpeek(obj->outstack);
mystackpop(obj->outstack);
return x;
}//The first element of the pop queue is the bottom element of the stack, so pop out all the elements in the instack and push them into the outstack. When the outstack is not empty, the first element of the queue can only be at the top of the outstack, not in the instack

int myQueuePeek(MyQueue* obj) {
if(mystackempty(obj->outstack))
{
    in2out(obj);
}
int x=mystackpeek(obj->outstack);
return x;
}//There are only two cases for the queue head element. One is to only push the queue that has not been popped. At this time, the overstack is empty, and the queue head element is at the bottom of the stack of instack and recorded with front. The other is that it has been popped, so the overstack is not empty, and the queue head element is at the top of the stack of overstack

bool myQueueEmpty(MyQueue* obj) {
return mystackempty(obj->instack)&&mystackempty(obj->outstack);
}

void myQueueFree(MyQueue* obj) {
mystackfree(obj->instack);
mystackfree(obj->outstack);
}

Note that when applying for space, you should also apply for space for stack

Auxiliary stack

First question

//Maintain prefix and array (product)
typedef struct {
int zeroindex;
int top;
int a[40001];
} ProductOfNumbers;


ProductOfNumbers* productOfNumbersCreate() {
ProductOfNumbers*ret=(ProductOfNumbers*)malloc(sizeof(ProductOfNumbers));
ret->zeroindex=-1;
ret->top=0;
return ret;
}

void productOfNumbersAdd(ProductOfNumbers* obj, int num) {
obj->a[obj->top]=num;
if(num==0)
{
    obj->a[obj->top]=1;
    obj->zeroindex=obj->top;
}
else
{
    obj->a[obj->top]=num*obj->a[obj->top-1];
}
(obj->top)++;
}

int productOfNumbersGetProduct(ProductOfNumbers* obj, int k) {
if(obj->zeroindex>obj->top-k-1)
{
    return 0;//Description the last k have 0
}
else{
    return obj->a[obj->top-1]/obj->a[obj->top-1-k];
}
}

void productOfNumbersFree(ProductOfNumbers* obj) {
free(obj);
}

Construct prefix and array, record top and zeroindex (the subscript of the nearest 0)

Second question

It's too difficult. It's not like the problem I can do

Monotonic stack, the acii code of the elements in the stack increases monotonically

As with the previous monotonic stack, if the traversal element is larger than the ascii code of the top element of the stack and the top element will appear later (implemented by recording lastindex in the hash table), remove the top elements one by one

If traversal elements already appear in the stack, skip directly (obtained from bool visited [26])

Maximum rectangle

First question

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n);
        
        stack<int> mono_stack;
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
            mono_stack.push(i);
        }

        mono_stack = stack<int>();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.empty() ? n : mono_stack.top());
            mono_stack.push(i);
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
};

The idea is to traverse i columns, find the first column on his left and right that is greater than its height, and then calculate the maximum area of each column

First traverse from left to right. If the monotone stack is not empty and the traversal element is less than or equal to the top element of the stack

Remove the stack top element when it is less than (note while)

Then update the left [i] (i.e. stack top) of the currently traversed I element and insert I

Use the same method to traverse from right to left and record the data on the left

int gettop(int*a,int top)
{
    return a[top-1];
}

int largestRectangleArea(int* heights, int heightsSize){
int stack[100001];
int top=0;
int*left=(int*)malloc(sizeof(int)*heightsSize);
int*right=(int*)malloc(sizeof(int)*heightsSize);
memset(left,0,sizeof(left));
memset(right,0,sizeof(left));
for(int i=0;i<heightsSize;i++)
{
    while(top!=0&&heights[i]<=heights[gettop(stack,top)])
    {
--top;
    }
    left[i]=top==0?-1:gettop(stack,top);
    stack[top++]=i;
}
int stack2[100001];
int top2=0;
for(int i=heightsSize-1;i>=0;--i)
{
    while(top2!=0&&heights[i]<=heights[gettop(stack2,top2)])
    {
--top2;
    }
    right[i]=top2==0?heightsSize:gettop(stack2,top2);
    stack2[top2++]=i;
}
int ans=0;
for(int i=0;i<heightsSize;++i)

{
    int temp=heights[i]*(right[i]-left[i]-1);
    ans=ans>temp?ans:temp;
}
return ans;
}

I wrote the c language version myself, although the boundary overflowed

Compare with daily temperature

The elements in the monotonic stack are monotonically increasing or decreasing. After traversal, they are compared with the elements at the top of the stack to decide whether to remove the elements at the top of the stack, update the value of the corresponding subscript of the array, and then put the traversal elements into the stack

It is suitable for the first subscript on the left and right that is greater than or less than this value

It's been a month. I really didn't expect to last for a month

Tags: C data structure

Posted by davitz38 on Sat, 30 Apr 2022 20:38:16 +0300