Finding minumum Element in einem Stapel in konstanter Zeit

Question

Wenn ich will, in konstanter Zeit ein Minimum Element in einem Stapel (Integer-Schlüssel), finden, dann kann es wie folgt erfolgen:

arr = [ 10, 7, 15, 12, 5 ] 

min_stack = [] 
main_stack = [] 

def get_min(): 
    if len(min_stack) < 1: 
     return None 
    return min_stack[-1] 

def push(key): 
    main_stack.append(key) 
    if len(min_stack) < 1 or min_stack[-1] > key: 
     min_stack.append(key) 


def pop(): 
    key = main_stack.pop() 
    min = get_min() 
    if key == min: 
     min_stack.pop() 
    return key 

for key in arr: 
    push(key)  

In der obigen Lösung Es ist möglich, min Wertelement in O(1) herauszufinden, aber es verwendet einen Hilfsspeicher der Größe n.

Gibt es einen Weg, dass es ohne Verwendung einer n Größe Speicher oder sagen Konstanten Speicher, durch Ausnutzung der arithmetischen Eigenschaften der Integer-Taste erfolgen kann.

Answer 1

Da es nicht anders angegeben war, dachte ich, ich würde eine Lösung hinzufügen, wenn der Bereich der ganzen Zahlen, die auf den Stack geschoben wurden, auf 32 Bit auf einem 64-Bit-System beschränkt war.

Ich weiß, dass diese Einschränkungen möglicherweise nicht anwendbar sind, aber ich werde dies hier lassen, falls es zu anderen Ideen führt.

Hinweis Wenn die Stapelwerte nicht beschränkt waren nur ganze Zahlen sind, dann könnte ein Tupel als auch in ähnlicher Weise verwendet werden, wo ein Stoß x ein Stoß (min_thus_far, x) zum Beispiel sein würde.

arr = [10, 7, 15, 12, 3, 21] 

main_stack = [] 

def get_min(): 
    if len(main_stack) == 0: 
     return None 
    return main_stack[-1] >> 32 

def push(key): 
    current_min = get_min() 
    if current_min: 
     if key < current_min: 
      current_min = key 
    else: 
     current_min = key 
    main_stack.append(key + (current_min << 32)) 

def pop(): 
    key = main_stack.pop() 
    return key & 0xFFFFFFFF 

for key in arr: 
    push(key) 

def print_state(): 
    print(", ".join(str(x & 0xFFFFFFFF) for x in main_stack)) 
    print("min: %d" %(get_min(),)) 

for _ in arr: 
    print_state() 
    print "popped:", pop() 

OUTPUT:

10, 7, 15, 12, 3, 21 
min: 3 
popped: 21 
10, 7, 15, 12, 3 
min: 3 
popped: 3 
10, 7, 15, 12 
min: 7 
popped: 12 
10, 7, 15 
min: 7 
popped: 15 
10, 7 
min: 7 
popped: 7 
10 
min: 10 
popped: 10 

Und hier ist ein Tupel Version:

arr = [10, 7, 15, 12, 3, 21] 

main_stack = [] 

def get_min(): 
    if len(main_stack) == 0: 
     return None 
    return main_stack[-1][0] 

def push(key): 
    current_min = get_min() 
    if current_min: 
     if key < current_min: 
      current_min = key 
    else: 
     current_min = key 
    main_stack.append((current_min, key)) 

def pop(): 
    key = main_stack.pop() 
    return key[1] 

for key in arr: 
    push(key) 

def print_state(): 
    print(", ".join(str(x[1]) for x in main_stack)) 
    print("min: %d" %(get_min(),)) 

for _ in arr: 
    print_state() 
    print "popped:", pop() 

Answer 2

Sie können es ohne O(n) Speicher in O(1) tun, wenn Sie nur eine einzige min speichern möchten Wert aller gedrückten Elemente.

Wenn Sie einen Verlauf von min Elementen speichern möchten, gibt es keinen anderen Weg, als eine Hilfsdatenstruktur zu verwenden, um sie zu halten. In diesem Fall ist die Verwendung des Stapels optimal, da Sie die Zeit O(1) drücken/einfügen können, was die Methode ist, die Sie verwenden.

Abgesehen: Ihr Code enthält einen kleinen Fehler:

Mit Ihrem Array arr = [2, 2] nach 2 Schübe, min_stack = [2]

Wenn Sie das erste Mal, Pop, min_stack = [] und main_stack = [2] get_min() wird None So zurückkehren, nicht 2.

Um es zu beheben, push_key ändern:

if len(min_stack) < 1 or min_stack[-1] >= key: