7

私がこの質問をしている理由は、私が考える方法がこの特定の質問に適用できない理由がわからないためです。

「プッシュとポップに加えて、最小要素を返す関数minも持つスタックをどのように設計しますか？プッシュ、ポップ、およびminはすべてO（1）時間で動作する必要があります。」

私の基本的な解決策：スタッククラスに変数がある場合、アイテムをスタックにプッシュするときはいつでも、それが最小変数よりも小さいかどうかを確認することはできません。最小値に値を割り当てる場合、無視しない場合。

min関数のようにO（1）を取得します。

int getMinimum(){
  return min;
}

なぜこの解決策が言及されないのですか、または私が考える方法の欠点は何ですか？

4

3 に答える 3

26

スタックから数字をポップした場合、これは機能しません。

元。2,4,5,3,1。あなたが1をポップした後、あなたの最小値は何ですか？

解決策は、単一の値だけでなく、最小値のスタックを保持することです。現在の最小値よりも小さい値に遭遇した場合は、それを最小スタックにプッシュする必要があります。

元。

Push(4):
Stack: 4
Min-stack: 4

Push(2):
Stack: 4 2
Min-stack: 4 2

Push(2):
Stack: 4 2 2
Min-stack: 4 2 2

Push(5):
Stack: 4 2 2 5
Min-stack: 4 2 2

Push(3):
Stack: 4 2 2 5 3
Min-stack: 4 2 2

Push(1):
Stack: 4 2 2 5 3 1
Min-stack: 4 2 2 1

Pop():
Stack: 4 2 2 5 3
Min-stack: 4 2 2

Pop():
Stack: 4 2 2 5
Min-stack: 4 2 2

Pop():
Stack: 4 2 2
Min-stack: 4 2 2

Pop():
Stack: 4 2
Min-stack: 4 2

Pop():
Stack: 4
Min-stack: 4
于 2012-11-04T22:27:36.007 に答える
1

リンクリストを使用して、先頭になる最小値を追跡します。

linkedlist.app = append（値をテールに入れます）に注意してください。linkedlist.pre = prepend（リンクリストの先頭として値を入れます）

パブリッククラススタック{

int[] elements;
int top;
Linkedlists min;

public Stack(int n) {
    elements = new int[n];
    top = 0;
    min = new Linkedlists();
}

public void realloc(int n) {
    int[] tab = new int[n];
    for (int i = 0; i < top; i++) {
        tab[i] = elements[i];
    }

    elements = tab;
}

public void push(int x) {
    if (top == elements.length) {
        realloc(elements.length * 2);
    }
    if (top == 0) {
        min.pre(x);
    } else if (x < min.head.data) {
        min.pre(x);
    } else {
        min.app(x);
    }
    elements[top++] = x;
}

public int pop() {

    int x = elements[--top];
    if (top == 0) {

    }
    if (this.getMin() == x) {
        min.head = min.head.next;
    }
    elements[top] = 0;
    if (4 * top < elements.length) {
        realloc((elements.length + 1) / 2);
    }

    return x;
}

public void display() {
    for (Object x : elements) {
        System.out.print(x + " ");
    }

}

public int getMin() {
    if (top == 0) {
        return 0;
    }
    return this.min.head.data;
}

public static void main(String[] args) {
    Stack stack = new Stack(4);
    stack.push(2);
    stack.push(3);
    stack.push(1);
    stack.push(4);
    stack.push(5);
    stack.pop();
    stack.pop();
    stack.pop();
    stack.push(1);
    stack.pop();
    stack.pop();
    stack.pop();
    stack.push(2);
    System.out.println(stack.getMin());
    stack.display();

}

}

于 2017-02-26T09:14:44.313 に答える
0

私はここでこの解決策を見つけました

struct StackGetMin {
  void push(int x) {
    elements.push(x);
    if (minStack.empty() || x <= minStack.top())
      minStack.push(x);
  }
  bool pop() {
    if (elements.empty()) return false;
    if (elements.top() == minStack.top())
      minStack.pop();
    elements.pop();
    return true;
  }
  bool getMin(int &min) {
    if (minStack.empty()) {
      return false;
    } else {
      min = minStack.top();
      return true;
    }
  }
  stack<int> elements;
  stack<int> minStack;
};
于 2014-10-09T04:27:45.513 に答える