leetcode/algorithms/min_stack.cpp at master · hanfezh/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 155. Min Stack: https://leetcode.com/problems/min-stack
// Author: xianfeng.zhu@gmail.com

#include <algorithm>
#include <climits>

#include "gmock/gmock.h"
#include "gtest/gtest.h"

class MinStack {
  struct Node {
    int val;
    int min;
    Node* next;
    Node(int _val, int _min, Node* _next = nullptr) : val(_val), min(_min), next(_next) {}
  };

 public:
  MinStack() : head_(nullptr) {}

  void push(int x) {
    if (head_ == nullptr) {
      head_ = new Node(x, x);
    } else {
      head_ = new Node(x, std::min(head_->min, x), head_);
    }
  }

  void pop() {
    auto* ptr = head_;
    head_ = head_->next;
    delete ptr;
  }

  int top() { return head_->val; }

  int getMin() { return head_->min; }

 private:
  Node* head_;
};

TEST(Solution, MinStack) {
  MinStack min_stack;
  min_stack.push(-2);
  min_stack.push(0);
  min_stack.push(-3);
  EXPECT_EQ(min_stack.getMin(), -3);

  min_stack.pop();
  EXPECT_EQ(min_stack.top(), 0);
  EXPECT_EQ(min_stack.getMin(), -2);
}