155. Min Stack

2019-11-08 03:01:55

字体：大中小

来源：转载

供稿：网友

题目

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. Example: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); –> Returns -3. minStack.pop(); minStack.top(); –> Returns 0. minStack.getMin(); –> Returns -2. Subscribe to see which companies asked this question.

思路

搞两个stack，一个存正常的stack值，另一个存当前stack个数对应的最小值

代码

class MinStack { //思路，两个stack，一个存数据，一个存stack里有n个数据时候对应的最小值 stack<int> numStack; stack<int> minStack;public: void push(int x) { numStack.push(x); if(minStack.empty()) { minStack.push(x); } else { if(minStack.top() < x) { minStack.push(minStack.top()); } else { minStack.push(x); } } } void pop() { numStack.pop(); minStack.pop(); } int top() { return numStack.top(); } int getMin() { return minStack.top(); }};

上一篇：node.js错误 --> node-pre-gyp install --fallback-to-build

下一篇：把二叉树打印成多行