---答题基础知识储备---
栈:又名堆栈,是一种运算受限的线性表,限定仅允许在表头进行插入和删除操作。
栈的基本算法:栈一般有两种基本操作,“入栈”和“出栈”。
入栈(PUSH)算法:
入栈前,首先检查栈是否已满,若栈满(TOP>n),则给出溢出信息,做出错处理;若不满,则执行步骤2;
栈指针+1,指向进栈地址(TOP = TOP+1);
将S(TOP)指向新进栈元素(S(TOP)=X),元素进栈结束;
出栈(POP)算法:
出栈前先检查栈是否已空,如果栈已空(TOP<0),则给出下溢信息,做出错处理;若非空,则执行步骤2;
将出栈的元素赋值给取它的变量(X=S(TOP));
栈指针-1,指向栈顶(TOP=TOP-1);
------
题目:
设计一个包含min函数的栈。定义栈的数据结构,要求添加一个min函数能够得到栈的最小元素;要求函数min、push以及pop的时间复杂度都是O(1)。
答题分析:
本题是要设计一个“栈”,根据栈的特性,先入栈的元素后出栈,另外,栈内要有一个min函数,用于获取当前栈内的最小元素。
哎呀,这个题的题干把我给绕住了...min函数的作用是获取当前栈中的最小元素,题干中没有说“当前”两个字,但是应该是这个意思,所以我进了一个误区。
看到题目我的第一反应,是设置一个min系统变量,在push时用来存储最小值的位置;但是,仔细一想,这样做有一个问题,全部元素push入栈之后,min变量确定的最小值,在pop时有可能被弹出,min变量标记的最小值被弹出后,如何获得当前栈中的最小值?
所以,min系统变量的方式是不行的,考虑到push入栈和pop出栈时,当前栈中的最小值都是在变化的,所以,可以用一个min辅助栈来保存变化中的最小值。
解答:
设计一个数据栈StackData和一个最小值辅助栈StackMin,
PUSH操作:
在每次向StackData中push入栈数据时,比较一下当前StackMin的栈顶元素:若StackMin栈顶元素为空,则push数据直接入两栈;若push值大于栈顶元素,则只入StackData栈;若push值小于等于StackMin栈顶元素,则push数据入两栈。
POP操作
出栈操作时,比较StackData中栈顶元素和StackMin中栈顶元素的值,如果两值相等,则共同出栈,若不相等,则只StackData栈顶元素出栈;getMin操作
经过以上两种操作,即可知StackMin栈顶元素始终为StackData中的最小值,getMin操作即是获取StackMin的栈顶元素
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | typedef struct { int val; int min; }stack_item; typedef struct { stack_item data[STACK_LEN]; int top; }stack; void push(stack *stk, int val){ stk->data[++stk->top].val = val; if (stk->top > 0){ if (val < stk->data[stk->top -1].min){ // 如果push进的元素小于最小元素 skt->data[stk->top].min = val; //将当前元素置为栈中最小元素 } else { //否则,不更新最小元素 skt->data[stk->top].min = skt->data[stk->top-1].min; } } else { skt->data[stk->top].min = val; } } int pop(stack *stk){ return stk->data[skt->top--].val; } int min(stack *stk){ return stk->data[skt->top].min; } |
以上用辅助栈的方法是这道题目的传统解法,另外还有一种巧妙的解法,不用辅助栈
解法思路:
push(int elem)入栈元素时,向栈中压入当前元素与最小元素的差值,然后比较当前元素与当前最小元素的大小,并将它们之间的最小值压入。
执行pop()函数,元素出栈操作时,先pop()出栈顶的两个值,这两个值分别是当前栈中最小值min和最后压入的元素与栈中最小值的差值diff。
如果diff<0,则表示最后压入栈的元素是当前栈的最小元素,弹出栈后,此时,栈中的最小元素大小为(min - diff);将(min - diff)压入栈,弹出min,完成pop()操作。
如果diff>=0且栈不为空,则表示最后压入栈的元素不是当前栈的最小元素,此时需要弹出的元素值为(min + diff);将(min + diff)弹出,将min压回栈。
如果栈为空,则表示当前元素已是栈中最后一个元素,直接弹出min即可。
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | struct minStackLessSpace{ void push( int i){ if (s.empty()){ s.push(i); s.push(i); } if (i-s.top()<0){ s.pop(); s.push(i-s.top()); s.push(i); } else { j=s.top(); s.pop(); s.push(i-s.top()); s.push(j); } } bool pop(){ if (s.empty()){ return false ;} int i = s.top(); s.pop(); if (s.top()<0){ int j = s.top(); s.pop(); s.push(i-j); } else { s.pop(); s.push(i); } } int min() { int min = s.top(); return min; } }
|
友情提示:垃圾评论一律封号...