LeetCode 155 Min Stack (특수 조작 이 있 는 스 택 실현)

1840 단어 데이터 구조
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack.

  • Example:
    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin();   --> Returns -3.
    minStack.pop();
    minStack.top();      --> Returns 0.
    minStack.getMin();   --> Returns -2.

    제목: push, pop, top 및 getMin (스 택 에서 최소 요소 로 돌아 가기) 작업 을 지원 하 는 스 택 을 실현 합 니 다.
    문제 풀이 방향: 동적 배열 시 뮬 레이 션 스 택 을 이용 하여 매번 push 작업 을 할 때마다 하나의 구조 체 를 스 택 에 넣 습 니 다. 구조 체 에는 현재 스 택 요소 와 현재 스 택 에 있 는 요소 의 최소 값 을 포함 합 니 다.모든 작품 은 상수 시간 만 필요 하 다.
    코드 는 다음 과 같 습 니 다:
    typedef struct {
        int val;
        int min;
    } Node;
    
    typedef struct {
        Node *arr;
        int top;
        int size;
    } MinStack;
    
    /** initialize your data structure here. */
    MinStack *minStackCreate(int maxSize) {
        MinStack *mstk = (MinStack *) malloc(sizeof *mstk);
        mstk->arr = (Node *) malloc(sizeof(Node) * (maxSize + 1));
        mstk->arr[0].min = INT_MAX;
        mstk->size = maxSize;
        mstk->top = 0;
        return mstk;
    }
    
    void minStackPush(MinStack *obj, int x) {
        obj->arr[++obj->top].val = x;
        if (obj->arr[obj->top-1].min > x) obj->arr[obj->top].min = x;
        else obj->arr[obj->top].min = obj->arr[obj->top-1].min;
    }
    
    void minStackPop(MinStack *obj) {
        obj->top--;
    }
    
    int minStackTop(MinStack *obj) {
        return obj->arr[obj->top].val;
    }
    
    int minStackGetMin(MinStack *obj) {
        return obj->arr[obj->top].min;
    }
    
    void minStackFree(MinStack *obj) {
        free(obj->arr);
        free(obj);
    }

    좋은 웹페이지 즐겨찾기