Min Stack
概要
stackを作り、最小値を返すメソッドも作れという問題
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
解法
昔↓と解いていたが、問題の制約として
You must implement a solution with O(1) time complexity for each function.
があり、getMin()の実装で時間計算量O(N)かかっており制約を守れていなかった
code:solution.cpp
class MinStack {
public:
vector<int> vec;
MinStack() {
vec = {};
}
void push(int x) {
vec.push_back(x);
}
void pop() {
vec.pop_back();
}
int top() {
return vec.back();
}
int getMin() {
auto iter = min_element(vec.begin(), vec.end());
return *iter;
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
時間計算量 O(1)を守るためにどう組むか分からなかったが解説で方法が紹介されていたので、それをヒントにGoで解き直したnixii.icon index 0: pushされた値
index1: pushされた時点まででの最小値
を保持する二重配列valuesを使うことで時間計算量 O(1)となっている
code:main.go
type MinStack struct {
// index 0: value
// index 1: min value
values [][]int
}
func Constructor() MinStack {
return MinStack{[][]int{}}
}
func (this *MinStack) Push(val int) {
minVal := val
if len(this.values) > 0 {
if prevMinVal < minVal { minVal = prevMinVal }
}
this.values = append(this.values, []int{val, minVal})
}
func (this *MinStack) Pop() {
}
func (this *MinStack) Top() int {
}
func (this *MinStack) GetMin() int {
}
/**
* Your MinStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/