编译环境
本系列文章所提供的算法均在以下环境下编译通过。
【算法编译环境】Federa 8,linux 2.6.35.6-45.fc14.i686
【处理器】 Intel(R) Core(TM)2 Quad CPU Q9400 @ 2.66GHz
【内存】 2025272 kB
前言
这是一道经常遇见的面试题。好像网易和google都曾出过此题。这道题解法也胜多。这里给出普遍的一种解法。即增加一个辅助堆栈来存储最小值。
本系列文章均系笔者所写,难免有一些错误或者纰漏,如果小伙伴们有好的建议或者更好的算法,请不吝赐教。
正文
【题目】
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
【例子】
【分析】
我第一次看到这个题目的时候,想用一个min变量保存最小的值就不OK了。再一想,如果这个最小元素被pop出去了,怎么办呢?
因此仅仅只添加一个成员变量存放最小元素(或最小元素的位置)是不够的。我们需要一个辅助栈。每次push一个新元素的时候,同时将最小元素(或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结构,用最小元素的位置将能减少空间消耗)push到辅助栈中;每次pop一个元素出栈的时候,同时pop辅助栈。
【代码】
#ifndef STACK_HPP #define STACK_SIZE 20 typedef struct {
int data[STACK_SIZE];
int top;
int min;
}Stack; void init( Stack *s );
void push( Stack *s, int val );
int pop( Stack *s );
bool full( Stack *s );
bool empty( Stack *s );
int min( Stack *s ); #endif
#include <iostream>
#include <cstdio>
#include <cstring>
#include "stack.hpp" Stack assist; void init( Stack *s )
{
s->top = -;
s->min = -; assist.top = -;
} void push( Stack *s ,int val )
{
if( full(s) )
{
printf("%s\n", "stack is full");
return;
}
if( (s->min == -) || (val < s->min) )
{
s->min = val;
assist.data[++assist.top] = val;
}
s->data[++s->top] = val;
} int pop( Stack *s )
{
int data;
if( empty(s) )
{
printf( "%s\n", "stack is empty" );
return -;
}
data = s->data[s->top--];
if( data == assist.data[assist.top] )
{
s->min = assist.data[--assist.top];
}
return data;
} bool full( Stack *s )
{
if( s->top == STACK_SIZE- )
{
return true;
}
return false;
} bool empty( Stack *s )
{
if( s->top == - )
{
return true;
}
return false;
} int min( Stack *s )
{
return s->min;
} int main( int argc, char ** argv )
{
Stack s;
init( &s );
push( &s, );
std::cout << min( &s ) << std::endl;
push( &s, );
std::cout << min( &s ) << std::endl;
push( &s, );
std::cout << min( &s ) << std::endl;
push( &s, );
std::cout << min( &s ) << std::endl;
pop( &s );
std::cout << min( &s ) << std::endl;
pop( &s );
std::cout << min( &s ) << std::endl;
push( &s, );
std::cout << min( &s ) << std::endl;
return ;
}
【结论】
我们做如下测试:
步骤 | 数据栈 | 辅助栈 | 最小值 |
1 | 3 | 3 | 3 |
2 | 3,4 | 3 | 3 |
3 | 3,4,2 | 3,2 | 2 |
4 | 3,4,2,1 | 3,2,1 | 1 |
5 | 3,4,2 | 3,2 | 2 |
6 | 3,4 | 3 | 3 |
7 | 3,4,0 | 3,0 | 0 |
作者
出处:http://www.cnblogs.com/gina
本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。