이것은 인터뷰 질문 중 하나입니다. getMinimum () 함수가 스택의 최소 요소를 반환하도록 정수 값을 보유하는 스택을 설계해야합니다.
예 : 아래 예를 고려하십시오.
사례 # 1 5-> 상단 1 4 6 2 getMinimum ()이 호출되면 최소 요소 인 1을 반환해야합니다. 스택에. 사례 # 2 stack.pop () stack.pop () 참고 : 5와 1은 모두 스택에서 튀어 나옵니다. 그래서 그 후 스택 마치 4-> 상단 6 2 getMinimum ()이 호출되면 최소값 인 2를 반환해야합니다. 스택.
공헌자 :
- getMinimum은 O (1)의 최소값을 반환해야합니다.
- 공간 제약도 설계시 고려해야하며 추가 공간을 사용하는 경우 일정한 공간이어야합니다.
답변
편집 : 이것은 “상수 공간”제약 조건에 실패합니다. 기본적으로 필요한 공간을 두 배로 늘립니다. 어딘가에서 런타임 복잡성을 해치지 않고 (예 : 푸시 / 팝 O (n) 만들기) 그렇게 하지 않는 솔루션이 있다는 것은 매우 의심 스럽습니다 . 이것은 필요한 공간 의 복잡성 을 변경하지 않습니다 . 예를 들어 O (n) 공간 요구 사항이있는 스택이있는 경우, 이것은 다른 상수 계수를 가진 O (n)입니다.
상수 공간이 아닌 솔루션
“스택에서 낮은 모든 값의 최소값”의 “중복”스택을 유지하십시오. 메인 스택을 팝할 때 최소 스택도 팝하십시오. 메인 스택을 푸시 할 때 새 요소 또는 현재 최소값 중 더 낮은 값을 푸시합니다. getMinimum()그런 다음 minStack.peek().
따라서 귀하의 예를 사용하면 다음과 같습니다.
Real stack Min stack
5 --> TOP 1
1 1
4 2
6 2
2 2
두 번 터지면 다음을 얻습니다.
Real stack Min stack
4 2
6 2
2 2
정보가 충분하지 않은 경우 알려주세요. 당신이 그것을 할 때 간단하지만 처음에는 약간의 머리를 긁을 수 있습니다. 🙂
(물론 단점은 공간 요구 사항을 두 배로 늘린다는 것입니다. 그러나 실행 시간은 크게 영향을받지 않습니다. 즉, 여전히 동일한 복잡성입니다.)
편집 : 약간 더 이상하지만 일반적으로 더 나은 공간이있는 변형이 있습니다. 우리는 여전히 min 스택을 가지고 있지만, 우리는 메인 스택에서 가져온 값이 min 스택의 값과 같을 때만 팝합니다. 우리는 푸시 메인 스택 미만이다 상 값이 밀려 최소 스택 같거나 현재의 최소값에 관한 것이다. 이렇게하면 최소값이 중복됩니다. getMinimum()여전히 엿보기 작업입니다. 예를 들어 원래 버전을 가져 와서 1을 다시 누르면 다음과 같은 결과가 나타납니다.
Real stack Min stack
1 --> TOP 1
5 1
1 2
4
6
2
1 == 1이기 때문에 위의 스택에서 팝은 두 스택에서 팝됩니다.
Real stack Min stack
5 --> TOP 1
1 2
4
6
2
다시 터지는 것은 5> 1이기 때문에 메인 스택 에서만 터집니다 .
Real stack Min stack
1 1
4 2
6
2
다시 팝하면 1 == 1이기 때문에 두 스택이 모두 팝됩니다.
Real stack Min stack
4 2
6
2
이것은 동일한 최악의 경우 공간 복잡성 (원래 스택의 두 배)으로 끝나지만 “새로운 최소값 또는 같음”을 거의 얻지 못하면 훨씬 더 나은 공간 사용으로 끝납니다.
편집 : 여기 Pete의 사악한 계획의 구현이 있습니다. 철저히 테스트하지는 않았지만 괜찮은 것 같아요 🙂
using System.Collections.Generic;
public class FastMinStack<T>
{
private readonly Stack<T> stack = new Stack<T>();
// Could pass this in to the constructor
private readonly IComparer<T> comparer = Comparer<T>.Default;
private T currentMin;
public T Minimum
{
get { return currentMin; }
}
public void Push(T element)
{
if (stack.Count == 0 ||
comparer.Compare(element, currentMin) <= 0)
{
stack.Push(currentMin);
stack.Push(element);
currentMin = element;
}
else
{
stack.Push(element);
}
}
public T Pop()
{
T ret = stack.Pop();
if (comparer.Compare(ret, currentMin) == 0)
{
currentMin = stack.Pop();
}
return ret;
}
}
답변
최소값을 유지할 필드를 추가하고 Pop () 및 Push () 중에 업데이트합니다. 이렇게하면 getMinimum ()은 O (1)이되지만 Pop ()과 Push ()는 조금 더 많은 작업을 수행해야합니다.
최소값이 팝되면 Pop ()은 O (n)이되고 그렇지 않으면 둘 다 O (1)이됩니다. 크기를 조정할 때 Push ()는 Stack 구현에 따라 O (n)이됩니다.
다음은 빠른 구현입니다.
public sealed class MinStack {
private int MinimumValue;
private readonly Stack<int> Stack = new Stack<int>();
public int GetMinimum() {
if (IsEmpty) {
throw new InvalidOperationException("Stack is empty");
}
return MinimumValue;
}
public int Pop() {
var value = Stack.Pop();
if (value == MinimumValue) {
MinimumValue = Stack.Min();
}
return value;
}
public void Push(int value) {
if (IsEmpty || value < MinimumValue) {
MinimumValue = value;
}
Stack.Push(value);
}
private bool IsEmpty { get { return Stack.Count() == 0; } }
}
답변
public class StackWithMin {
int min;
int size;
int[] data = new int[1024];
public void push ( int val ) {
if ( size == 0 ) {
data[size] = val;
min = val;
} else if ( val < min) {
data[size] = 2 * val - min;
min = val;
assert (data[size] < min);
} else {
data[size] = val;
}
++size;
// check size and grow array
}
public int getMin () {
return min;
}
public int pop () {
--size;
int val = data[size];
if ( ( size > 0 ) && ( val < min ) ) {
int prevMin = min;
min += min - val;
return prevMin;
} else {
return val;
}
}
public boolean isEmpty () {
return size == 0;
}
public static void main (String...args) {
StackWithMin stack = new StackWithMin();
for ( String arg: args )
stack.push( Integer.parseInt( arg ) );
while ( ! stack.isEmpty() ) {
int min = stack.getMin();
int val = stack.pop();
System.out.println( val + " " + min );
}
System.out.println();
}
}
현재 최소값을 명시 적으로 저장하고 최소값이 변경되면 값을 푸시하는 대신 새 최소값의 다른쪽에 동일한 차이를 푸시합니다 (최소 = 7이고 5를 누르면 대신 3을 푸시합니다 (5- | 7-5 | = 3) min을 5로 설정합니다. min이 5 일 때 3을 팝하면 팝된 값이 min보다 작다는 것을 알 수 있으므로 새로운 min에 대해 7을 얻는 절차를 반대로 한 다음 이전 값을 반환합니다. 최소). 변경을 유발하지 않는 값은 현재 최소값이 현재 최소값보다 크므로 최소값을 변경하는 값과 그렇지 않은 값을 구분하는 데 사용할 수있는 것이 있습니다.
고정 크기 정수를 사용하는 언어에서는 값 표현에서 약간의 공간을 차용하므로 언더 플로가 발생하여 어설 션이 실패합니다. 그러나 그렇지 않으면 일정한 추가 공간이며 모든 작업은 여전히 O (1)입니다.
대신 연결된 목록을 기반으로하는 스택에는 예를 들어 C에서 다음 포인터의 최하위 비트 또는 Java에서 연결 목록의 개체 유형을 빌릴 수있는 다른 위치가 있습니다. Java의 경우 링크 당 객체 오버 헤드가 있으므로 연속 스택에 비해 더 많은 공간이 사용됩니다.
public class LinkedStackWithMin {
private static class Link {
final int value;
final Link next;
Link ( int value, Link next ) {
this.value = value;
this.next = next;
}
int pop ( LinkedStackWithMin stack ) {
stack.top = next;
return value;
}
}
private static class MinLink extends Link {
MinLink ( int value, Link next ) {
super( value, next );
}
int pop ( LinkedStackWithMin stack ) {
stack.top = next;
int prevMin = stack.min;
stack.min = value;
return prevMin;
}
}
Link top;
int min;
public LinkedStackWithMin () {
}
public void push ( int val ) {
if ( ( top == null ) || ( val < min ) ) {
top = new MinLink(min, top);
min = val;
} else {
top = new Link(val, top);
}
}
public int pop () {
return top.pop(this);
}
public int getMin () {
return min;
}
public boolean isEmpty () {
return top == null;
}
C에서는 오버 헤드가 없으며 다음 포인터의 lsb를 빌릴 수 있습니다.
typedef struct _stack_link stack_with_min;
typedef struct _stack_link stack_link;
struct _stack_link {
size_t next;
int value;
};
stack_link* get_next ( stack_link* link )
{
return ( stack_link * )( link -> next & ~ ( size_t ) 1 );
}
bool is_min ( stack_link* link )
{
return ( link -> next & 1 ) ! = 0;
}
void push ( stack_with_min* stack, int value )
{
stack_link *link = malloc ( sizeof( stack_link ) );
link -> next = ( size_t ) stack -> next;
if ( (stack -> next == 0) || ( value == stack -> value ) ) {
link -> value = stack -> value;
link -> next |= 1; // mark as min
} else {
link -> value = value;
}
stack -> next = link;
}
etc.;
그러나 이들 중 어느 것도 진정한 O (1)이 아닙니다. 실제로는 더 이상 공간이 필요하지 않습니다. 이러한 언어의 숫자, 객체 또는 포인터 표현의 허점을 이용하기 때문입니다. 그러나 더 간결한 표현을 사용하는 이론적 인 기계는 각 경우에 해당 표현에 추가 비트를 추가해야합니다.
답변
언급 된 모든 제약 (일정 시간 작업)과 일정한 추가 공간 을 충족하는 솔루션을 찾았습니다 .
아이디어는 최소값과 입력 숫자의 차이를 저장하고 더 이상 최소값이 아닌 경우 최소값을 업데이트하는 것입니다.
코드는 다음과 같습니다.
public class MinStack {
long min;
Stack<Long> stack;
public MinStack(){
stack = new Stack<>();
}
public void push(int x) {
if (stack.isEmpty()) {
stack.push(0L);
min = x;
} else {
stack.push(x - min); //Could be negative if min value needs to change
if (x < min) min = x;
}
}
public int pop() {
if (stack.isEmpty()) return;
long pop = stack.pop();
if (pop < 0) {
long ret = min
min = min - pop; //If negative, increase the min value
return (int)ret;
}
return (int)(pop + min);
}
public int top() {
long top = stack.peek();
if (top < 0) {
return (int)min;
} else {
return (int)(top + min);
}
}
public int getMin() {
return (int)min;
}
}
크레딧 : https://leetcode.com/discuss/15679/share-my-java-solution-with-only-one-stack
답변
음, 런타임 제약 무엇 push과 pop? 상수 일 필요가없는 경우 두 작업에서 최소값을 계산하면됩니다 ( O ( n )). 그렇지 않으면 일정한 추가 공간으로 어떻게 할 수 있는지 알 수 없습니다.
답변
다음은 O (1)로 실행되는 코드입니다. 내가 게시 한 이전 코드는 최소 요소가 튀어 나올 때 문제가있었습니다. 코드를 수정했습니다. 이것은 현재 푸시 된 요소 위의 스택에있는 최소 요소를 유지하는 다른 스택을 사용합니다.
class StackDemo
{
int[] stk = new int[100];
int top;
public StackDemo()
{
top = -1;
}
public void Push(int value)
{
if (top == 100)
Console.WriteLine("Stack Overflow");
else
stk[++top] = value;
}
public bool IsEmpty()
{
if (top == -1)
return true;
else
return false;
}
public int Pop()
{
if (IsEmpty())
{
Console.WriteLine("Stack Underflow");
return 0;
}
else
return stk[top--];
}
public void Display()
{
for (int i = top; i >= 0; i--)
Console.WriteLine(stk[i]);
}
}
class MinStack : StackDemo
{
int top;
int[] stack = new int[100];
StackDemo s1; int min;
public MinStack()
{
top = -1;
s1 = new StackDemo();
}
public void PushElement(int value)
{
s1.Push(value);
if (top == 100)
Console.WriteLine("Stack Overflow");
if (top == -1)
{
stack[++top] = value;
stack[++top] = value;
}
else
{
// stack[++top]=value;
int ele = PopElement();
stack[++top] = ele;
int a = MininmumElement(min, value);
stack[++top] = min;
stack[++top] = value;
stack[++top] = a;
}
}
public int PopElement()
{
if (top == -1)
return 1000;
else
{
min = stack[top--];
return stack[top--];
}
}
public int PopfromStack()
{
if (top == -1)
return 1000;
else
{
s1.Pop();
return PopElement();
}
}
public int MininmumElement(int a,int b)
{
if (a > b)
return b;
else
return a;
}
public int StackTop()
{
return stack[top];
}
public void DisplayMinStack()
{
for (int i = top; i >= 0; i--)
Console.WriteLine(stack[i]);
}
}
class Program
{
static void Main(string[] args)
{
MinStack ms = new MinStack();
ms.PushElement(15);
ms.PushElement(2);
ms.PushElement(1);
ms.PushElement(13);
ms.PushElement(5);
ms.PushElement(21);
Console.WriteLine("Min Stack");
ms.DisplayMinStack();
Console.WriteLine("Minimum Element:"+ms.StackTop());
ms.PopfromStack();
ms.PopfromStack();
ms.PopfromStack();
ms.PopfromStack();
Console.WriteLine("Min Stack");
ms.DisplayMinStack();
Console.WriteLine("Minimum Element:" + ms.StackTop());
Thread.Sleep(1000000);
}
}
답변
다른 종류의 스택을 사용했습니다. 다음은 구현입니다.
//
// main.cpp
// Eighth
//
// Created by chaitanya on 4/11/13.
// Copyright (c) 2013 cbilgika. All rights reserved.
//
#include <iostream>
#include <limits>
using namespace std;
struct stack
{
int num;
int minnum;
}a[100];
void push(int n,int m,int &top)
{
top++;
if (top>=100) {
cout<<"Stack Full";
cout<<endl;
}
else{
a[top].num = n;
a[top].minnum = m;
}
}
void pop(int &top)
{
if (top<0) {
cout<<"Stack Empty";
cout<<endl;
}
else{
top--;
}
}
void print(int &top)
{
cout<<"Stack: "<<endl;
for (int j = 0; j<=top ; j++) {
cout<<"("<<a[j].num<<","<<a[j].minnum<<")"<<endl;
}
}
void get_min(int &top)
{
if (top < 0)
{
cout<<"Empty Stack";
}
else{
cout<<"Minimum element is: "<<a[top].minnum;
}
cout<<endl;
}
int main()
{
int top = -1,min = numeric_limits<int>::min(),num;
cout<<"Enter the list to push (-1 to stop): ";
cin>>num;
while (num!=-1) {
if (top == -1) {
min = num;
push(num, min, top);
}
else{
if (num < min) {
min = num;
}
push(num, min, top);
}
cin>>num;
}
print(top);
get_min(top);
return 0;
}
산출:
Enter the list to push (-1 to stop): 5
1
4
6
2
-1
Stack:
(5,5)
(1,1)
(4,1)
(6,1)
(2,1)
Minimum element is: 1
시도 해봐. 나는 그것이 질문에 대한 답이라고 생각합니다. 모든 쌍의 두 번째 요소는 해당 요소가 삽입되었을 때 표시되는 최소값을 제공합니다.
