LeetCodeに毎日挑戦してみた 155. Min Stack（Python、Go）
Leetcodeとは
leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。
golang入門＋アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)
35問目（問題155)
155. Min Stack
問題内容
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.
日本語訳
プッシュ、ポップ、トップ、および最小要素の一定時間での取得をサポートするスタックを設計します。
- push（x）-要素xをスタックにプッシュします。
- pop（）-スタックの一番上の要素を削除します。
- top（）-最上位の要素を取得します。
- getMin（）-スタック内の最小要素を取得します。
Example 1:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
考え方
- 問題文を読んで理想の戻り値、配列の処理を把握します
- 貯められた数字と、貯めた数字の中で最小の数字を保持する必要があります。
- 一番目にその数字、二番目に最小の数字を保持しながらpopやpushを実装します。
解答コード
class MinStack:
def __init__(self):
self.q = []
# @param x, an integer
# @return an integer
def push(self, x):
curMin = self.getMin()
if curMin == None or x < curMin:
curMin = x
self.q.append((x, curMin));
# @return nothing
def pop(self):
self.q.pop()
# @return an integer
def top(self):
if len(self.q) == 0:
return None
else:
return self.q[len(self.q) - 1][0]
# @return an integer
def getMin(self):
if len(self.q) == 0:
return None
else:
return self.q[len(self.q) - 1][1]
- Goでも書いてみます！
type MinStack struct {
vals [][]int
}
/** initialize your data structure here. */
func Constructor() MinStack {
return MinStack{vals: [][]int{}}
}
func (this *MinStack) Push(x int) {
if len(this.vals) == 0 {
this.vals = [][]int{{x, x}}
} else {
this.vals = append(this.vals, []int{x, min(x, this.GetMin())})
}
}
func (this *MinStack) Pop() {
this.vals = this.vals[:len(this.vals)-1]
}
func (this *MinStack) Top() int {
return this.vals[len(this.vals)-1][0]
}
func (this *MinStack) GetMin() int {
return this.vals[len(this.vals)-1][1]
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
Author And Source
この問題について(LeetCodeに毎日挑戦してみた 155. Min Stack（Python、Go）), 我々は、より多くの情報をここで見つけました https://qiita.com/ishishow/items/bb7d9bee890b32879828著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .