검 지 offer - 30. min 함 수 를 포함 하 는 창고 | 31. 창고 의 압 입, 팝 업 시퀀스

면접 문제 30. min 함 수 를 포함 하 는 스 택
제목 설명: 스 택 의 데이터 구 조 를 정의 합 니 다. 이 유형 에서 스 택 에 포 함 된 최소 요 소 를 얻 을 수 있 는 min 함수 (시간 복잡 도 는 O (1) 를 실현 하 십시오.메모: 테스트 중 스 택 이 비어 있 을 때 스 택 에 pop () 또는 min () 또는 top () 방법 을 호출 하지 않도록 합 니 다.

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

문제 풀이 방향:

       ，    ，  A     B    ，B   ；
    ，AB     ，  ，
  ，AB      ，A ，B  。

class Solution {
public:
     
    stack<int> stack1,stack2;
     
    void push(int value) {
        stack1.push(value);
        if(stack2.empty())
            stack2.push(value);
        else if(value<=stack2.top())
        {
            stack2.push(value);
        }
    }
     
    void pop() {
        if(stack1.top()==stack2.top())
            stack2.pop();
        stack1.pop();
         
    }
     
    int top() {
        return stack1.top();       
    }
     
    int min() {
        return stack2.top();
    }
     
};

면접 문제 31. 창고 의 압축, 팝 업 시퀀스
제목 설명: 두 개의 정수 서열 을 입력 하 십시오. 첫 번 째 서열 은 창고 의 압축 순 서 를 표시 합 니 다. 두 번 째 서열 이 창고 의 팝 업 순서 가 될 수 있 는 지 판단 하 십시오.창고 에 쌓 인 모든 숫자 가 같 지 않다 고 가정 하 세 요.예 를 들 어 서열 1, 2, 3, 4, 5 는 특정한 스 택 의 압 입 순서 이 고 서열 4, 5, 3, 2, 1 은 이 스 택 서열 에 대응 하 는 팝 업 서열 이지 만 4, 3, 5, 1, 2 는 이 스 택 서열 의 팝 업 서열 일 수 없다.(주의: 이 두 서열 의 길 이 는 같다)

   1：

  ：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
  ：true
  ：           ：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

   2：

  ：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
  ：false
  ：1     2     。

문제 풀이 방향:

      ：        ，             ，       ，
         ，              。
        ，  ，                  。
  ，                   。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.empty() || popV.empty() || pushV.size()!=popV.size())
            return false;
        stack<int> s;
        int j=0;
        for(int i=0;i<pushV.size();++i){
            s.push(pushV[i]);
            while(!s.empty()&&s.top()==popV[j]){
                s.pop();
                ++j;
            }
        }
        if(s.empty())
            return true;
        return false;
    }
};

참조 링크:https://www.nowcoder.com/profile/8801548/codeBookDetail?submissionId=16793789