血色星期一3,地缚灵的童养媳,黄泉迷情
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.
写一个小堆栈,本身没有什么难度,这道题比较特殊的地方是要求 getMin() 的执行时间是
为了达到这个要求,就需要将这些最小元素存储下来。下面的代码中用了两个 vector ,一个存放所有的数据,另一个只存中间这些所谓的最小元素。
这样,在任意时刻,m_min 的栈顶都存放的是 m_stack 最小元素。每次 getMin() 时只需返回 m_min 的栈顶元素就可以了。
class MinStack { public: /** initialize your data structure here. */ MinStack() { } void push(int x) { m_stack.push_back(x); if(m_min.empty() || x <= m_min.back()) { m_min.push_back(x); } } void pop() { if(!m_stack.empty()) { int x = m_stack.back(); m_stack.pop_back(); if(x == m_min.back()) { m_min.pop_back(); } } } int top() { if(!m_stack.empty()) { return m_stack.back(); } return 0; } int getMin() { if(!m_min.empty()) { return m_min.back(); } return 0; } private: vector m_stack; vector m_min; };
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论