最小棧的實(shí)現(xiàn)

思路

兩個(gè)棧，左邊棧接受元素，右邊棧存最小的元素

入棧時(shí)，先入左邊棧，隨后進(jìn)行比較，左邊和右邊棧頂元素進(jìn)行比較，如果新元素小，就把新元素放在右邊的棧頂位置，如果新元素大，則還是把右邊棧頂元素放在棧頂?shù)奈恢?/li>

出棧時(shí)，出的是最后一個(gè)入棧元素，所以就是左邊的棧出棧

出最小值時(shí)，就是右邊的棧頂元素出棧

出棧時(shí)兩個(gè)都得出

class MinStack { public:/** initialize your data structure here. */MinStack() {}void push(int x) {left.push(x);int min;if (!right.empty() && right.top() <= x){min = right.top();}else{min = x;}right.push(min);}void pop() {left.pop();right.pop();}int top() {return left.top();}int getMin() {return right.top();}stack<int> left; //存正長(zhǎng)的數(shù)據(jù)stack<int> right; //存最小的數(shù)據(jù) };

優(yōu)化版本

class MinStack { public:/** initialize your data structure here. */MinStack() {}void push(int x) {left.push(x);if (right.empty() || x <= right.top()){right.push(x);}}void pop() {int top = left.top(); //先讓左邊出棧并記錄元素left.pop(); if (top == right.top()){ //如果左邊出棧得元素等于右邊棧頂元素，右邊才出right.pop();}}int top() {return left.top();}int getMin() {return right.top();}stack<int> left; //存正長(zhǎng)的數(shù)據(jù)stack<int> right; //存最小的數(shù)據(jù) };

總結(jié)

以上是生活随笔為你收集整理的最小栈的实现（设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。