LeetCode 155-最小スタック-Python
1094 ワード
タイトル
push,pop,top操作をサポートし,定数時間で最小要素を取得できるスタックを設計した. push(x)--要素xをスタックにプッシュします. pop()--スタックトップの要素を削除します. top()--スタックトップ要素を取得します. getMin()--スタック内の最小要素を取得します.
例:
構想
配列実装を使用して、配列要素は(x,curMin)であり、スタックに入るたびに挿入される値xと現在のスタック内の最小値curMinがスタックに挿入されます.
Pythonコード
push,pop,top操作をサポートし,定数時間で最小要素を取得できるスタックを設計した.
例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> -3.
minStack.pop();
minStack.top(); --> 0.
minStack.getMin(); --> -2.
構想
配列実装を使用して、配列要素は(x,curMin)であり、スタックに入るたびに挿入される値xと現在のスタック内の最小値curMinがスタックに挿入されます.
Pythonコード
class MinStack(object):
def __init__(self):
self.q = []
def push(self, x):
curMin = self.getMin()
if curMin == None or x < curMin:
curMin = x
self.q.append((x, curMin))
def pop(self):
self.q.pop()
def top(self):
if len(self.q) == 0:
return None
else:
return self.q[-1][0]
def getMin(self):
if len(self.q) == 0:
return None
else:
return self.q[-1][1]