我问这个问题的原因是因为我不明白为什么我的思维方式不能适用于这一特定问题
”
我的基本解决方案：那岂不是可能的，如果我们在栈类变量，每当我们推到堆栈我们会检查它是否比我们分变小的项目。 如果是赋值给分，如果不能忽视。
你仍然会得到O（1）min函数会;
int getMinimum(){
return min;
}
为什么这个解决方案是从来不提，或者说是我的思维方式的错吗？
Answer 1:
如果弹出数从堆栈中这是行不通的。
防爆。 2,4,5,3,1。 当你弹出1关，您的最低的是什么？
解决的办法是保持一个堆栈最低的，而不仅仅是一个单一的价值。 如果遇到一个值，该值小于等于当前最小，需要将其推到最小堆栈。
防爆。
Push(4):
Stack: 4
Min-stack: 4
Push(2):
Stack: 4 2
Min-stack: 4 2
Push(2):
Stack: 4 2 2
Min-stack: 4 2 2
Push(5):
Stack: 4 2 2 5
Min-stack: 4 2 2
Push(3):
Stack: 4 2 2 5 3
Min-stack: 4 2 2
Push(1):
Stack: 4 2 2 5 3 1
Min-stack: 4 2 2 1
Pop():
Stack: 4 2 2 5 3
Min-stack: 4 2 2
Pop():
Stack: 4 2 2 5
Min-stack: 4 2 2
Pop():
Stack: 4 2 2
Min-stack: 4 2 2
Pop():
Stack: 4 2
Min-stack: 4 2
Pop():
Stack: 4
Min-stack: 4
Answer 2:
使用链表来跟踪它会是头部的最小值。
需要注意的是linkedlist.app =追加（我们把值尾）。 linkedlist.pre =预定（我们把值作为链表的头）
公共类堆栈{
int[] elements;
int top;
Linkedlists min;
public Stack(int n) {
elements = new int[n];
top = 0;
min = new Linkedlists();
}
public void realloc(int n) {
int[] tab = new int[n];
for (int i = 0; i < top; i++) {
tab[i] = elements[i];
}
elements = tab;
}
public void push(int x) {
if (top == elements.length) {
realloc(elements.length * 2);
}
if (top == 0) {
min.pre(x);
} else if (x < min.head.data) {
min.pre(x);
} else {
min.app(x);
}
elements[top++] = x;
}
public int pop() {
int x = elements[--top];
if (top == 0) {
}
if (this.getMin() == x) {
min.head = min.head.next;
}
elements[top] = 0;
if (4 * top < elements.length) {
realloc((elements.length + 1) / 2);
}
return x;
}
public void display() {
for (Object x : elements) {
System.out.print(x + " ");
}
}
public int getMin() {
if (top == 0) {
return 0;
}
return this.min.head.data;
}
public static void main(String[] args) {
Stack stack = new Stack(4);
stack.push(2);
stack.push(3);
stack.push(1);
stack.push(4);
stack.push(5);
stack.pop();
stack.pop();
stack.pop();
stack.push(1);
stack.pop();
stack.pop();
stack.pop();
stack.push(2);
System.out.println(stack.getMin());
stack.display();
}
}
Answer 3:
我发现这个解决方案在这里
struct StackGetMin {
void push(int x) {
elements.push(x);
if (minStack.empty() || x <= minStack.top())
minStack.push(x);
}
bool pop() {
if (elements.empty()) return false;
if (elements.top() == minStack.top())
minStack.pop();
elements.pop();
return true;
}
bool getMin(int &min) {
if (minStack.empty()) {
return false;
} else {
min = minStack.top();
return true;
}
}
stack<int> elements;
stack<int> minStack;
};
Answer 4:
我们定义一个变量minEle存储在堆栈中的当前最小元素。 现在，有趣的是，当最小的元素被删除如何处理这种情况。 为了解决这个问题，我们推动“2X - minEle”入堆栈，而不是X，使以前的最小元素，可以使用当前minEle并存储在堆栈的值进行检索。 下面是详细的步骤和工作的说明。
推（X）：将x插入在堆栈的顶部 。
If stack is empty, insert x into the stack and make minEle equal to x.
If stack is not empty, compare x with minEle. Two cases arise:
If x is greater than or equal to minEle, simply insert x.
If x is less than minEle, insert (2*x – minEle) into the stack
and make minEle equal to x.
For example, let previous minEle was 3.
Now we want to insert 2. We update minEle as 2 and insert 2*2 – 3 = 1 into the stack.
弹出（）：删除从堆栈的顶部的元件。
Remove element from top. Let the removed element be y. Two cases arise:
If y is greater than or equal to minEle,
the minimum element in the stack is still minEle.
If y is less than minEle, the minimum element now becomes
(2*minEle – y), so update (minEle = 2*minEle – y).
This is where we retrieve previous minimum from current minimum
and its value in stack. For example, let the element to be
removed be 1 and minEle be 2. We remove 1 and update minEle as 2*2 – 1 = 3.
/ Java program to implement a stack that supports
// getMinimum() in O(1) time and O(1) extra space.
import java.util.*;
// A user defined stack that supports getMin() in
// addition to push() and pop()
class MyStack
{
Stack<Integer> s;
Integer minEle;
// Constructor
MyStack() { s = new Stack<Integer>(); }
// Prints minimum element of MyStack
void getMin()
{
// Get the minimum number in the entire stack
if (s.isEmpty())
System.out.println("Stack is empty");
// variable minEle stores the minimum element
// in the stack.
else
System.out.println("Minimum Element in the " +
" stack is: " + minEle);
}
// prints top element of MyStack
void peek()
{
if (s.isEmpty())
{
System.out.println("Stack is empty ");
return;
}
Integer t = s.peek(); // Top element.
System.out.print("Top Most Element is: ");
// If t < minEle means minEle stores
// value of t.
if (t < minEle)
System.out.println(minEle);
else
System.out.println(t);
}
// Removes the top element from MyStack
void pop()
{
if (s.isEmpty())
{
System.out.println("Stack is empty");
return;
}
System.out.print("Top Most Element Removed: ");
Integer t = s.pop();
// Minimum will change as the minimum element
// of the stack is being removed.
if (t < minEle)
{
System.out.println(minEle);
minEle = 2*minEle - t;
}
else
System.out.println(t);
}
// Insert new number into MyStack
void push(Integer x)
{
if (s.isEmpty())
{
minEle = x;
s.push(x);
System.out.println("Number Inserted: " + x);
return;
}
// If new number is less than original minEle
if (x < minEle)
{
s.push(2*x - minEle);
minEle = x;
}
else
s.push(x);
System.out.println("Number Inserted: " + x);
}
};
// Driver Code
public class Main
{
public static void main(String[] args)
{
MyStack s = new MyStack();
s.push(3);
s.push(5);
s.getMin();
s.push(2);
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.peek();
}
}
请问这个方法工作的？
当被插入元素小于minEle，我们插入“2X - minEle”。 以笔记重要的是，2 - minEle永远是小于x（以下证明），即新minEle同时弹出了这个元素，我们将看到的东西不寻常的事件为弹出的元素小于minEle。 因此，我们将更新minEle
如何2 * X - minEle小于x在推（）？
X <我这就意味着X - 我<0
//两侧添加X
X - 我+ x <0的+ X
2 * X - 我<X
我们得出结论：可以在2 * X - 我<新我
虽然飞出，如果发现元素（Y）小于当前minEle，我们找到了新的minEle = 2 * minEle - 年。
prevMinEle如何以前的最小单元，是，2 * minEle - ÿ？
在流行（）为y的弹出元件？
//我们推Ÿ高达2倍 - prevMinEle。 这里
// prevMinEle是minEle y为插入前
Y = 2 * X - prevMinEle
minEle的//值达到等于x minEle = X。
新= 2 *我我 - ÿ
= 2*x - (2*x - prevMinEle)
= prevMinEle // This is what we wanted
文章来源: Retrieving the Min element in a stack in O(1) Time
