1.题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
思路：利用一个辅助栈来存放最小值
栈 3，4，2，5，1
辅助栈 3，2，1
每入栈一次，就与辅助栈顶比较大小，如果小就入栈，如果大就不入栈当前的辅助栈；当出栈时，辅助栈元素相等时也要出栈。
class Solution {
public:
stack<int> mystack1;//辅助栈
stack<int> minstack;//最小栈
void push(int value) {
if(minstack.empty()){
minstack.push(value);
} else if(minstack.top()>value){
minstack.push(value);
}
mystack1.push(value);
}
void pop() {
if(mystack1.top()==minstack.top()) minstack.pop();
mystack1.pop();
}
int top() {
return mystack1.top();
}
int min() {
// if(!minstack.empty())
return minstack.top();
}
};
2.两个数组实现MIN栈问题
题目：定义栈的数据结构，请在该栈中实现一个能够得到栈中最小元素的MIN函数。在该栈中，调用MIN、PUSH、POP的时间复杂度均是O（1）。
根据题目可以看出，本次我们涉及的数据结构是栈(Stack),先看一下栈的介绍：栈又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除，使其相邻的元素成为新的栈顶元素。
上面的描述很详细，简单点说就是一句话，栈是一种先入后出的数据结构，基于这个特点，每次先压入栈的元素，总是最后才被弹出的，而每次弹出的元素，也肯定是最后被压入的元素，基于这种特点，对栈做排序是比较麻烦的，同时也注意到，题目中要求的时间复杂度是O(1)，也就是说不能利用遍历去得到这个最小值，哪有人会说了，我们可以记录一个全局变量，初始值为压入栈中的第一个元素，然后每次压栈都比较该变量中的元素和压栈元素的大小，保证该全局变量中存的就是最小数值，这样的思路倒是满足时间复杂度为O(1)的要求，但如果做了弹栈操作呢？如果把栈中最小的元素弹出怎么办？这个时候你这个全局变量就废了，因此这种办法也是行不通滴。
那该怎么办呢？事实上在压栈操作时就把最小元素存起来的思路是没有问题的，但是却只考虑了 一个最小元素，没有考虑第二小元素，第三小元素等等，而为了保证在最小元素弹出的情况下，可以立马得到第二小元素，我们要借助一个辅助的存储空间来完成这件事。
假如我们存储元素的栈是DATA栈，用来存储最小元素的辅助结构是TEMP栈(选用栈是为了和DATA栈保持一致，也方便理解)，这样我们就有两个栈，大家也应该注意到我们的标题就是“两个数组来实现MIN栈”。现在数组就可以排上用场了。
数组应该是大家接触最多，使用最广的数据结构了，其定义简单，理解起来容易，直接通过下标访问数据，可以达到O(1)的时间复杂度，但同时数组也存在诸多缺陷，比如说大小一旦确定，就无法改变，使用过程中如果稍有不慎，就有可能越界带来不可预知的错误。但在我们这道题中，首先就是要做到利用一个数组来实现两个栈，有以下两种思路：
1、定义两个下标index1和index2，初始值index1 = 0， index2 = length - 1 ，其中length为数组长度，每次向栈1压入元素时，index1增1，每次向栈2压入元素时，index2减1，弹栈时相反，栈的最大深度为length的一半，这样相当于索引值都是指向了栈顶，满足要求；
2、同样还是定义两个索引值index1和index2，初始值index1 = 0， index2 = 1， 每次压栈时，相应的索引值都增2，弹栈时减2，相当于把一个数组一分为二，偶数位作为一个栈，奇数位作为一个栈，两个栈互不干扰，独立使用，也可以满足要求。
比较上述两种方法可以看到思路1更为灵活，且几乎不会浪费数组空间，假设两个栈的深度为M和N，若用思路2，则无论M和N的关系如何，都必然会浪费|M-N|个空间，而思路1则不会有这种问题，不过在我们这道题中，DATA栈和TEMP栈大小一样，实际上用那种思路都可以
reference: 数据结构与算法（三）两个数组实现MIN栈问题
3. 用一个数组实现两个堆栈，最大化利用空间
注意理解下标的关系。
/*****************************************************
* \file 数组实现两个堆栈.cpp
* \date 2017/03/17 23:02
* \author ranjiewen
* \contact: ranjiewen@outlook.com
* \问题描述：
用一个数组实现两个堆栈，要求最大利用数组空间，使数组只要有空间
入栈操作就可以成功。
* \问题分析：
两个栈分别从数组的两头开始向中间生长，当两个栈的栈顶指针相遇时，表示两个栈都满了 *****************************************************/ #include<stdio.h>
#include <stdlib.h> #define MAXSIVE 20
typedef int ElementType;
typedef struct DStack *DStack_;
struct DStack
{
ElementType Data[MAXSIVE];
int top1; //栈1的栈顶指针
int top2; //栈2的栈顶指针
}; void Push(struct DStack *ptrs, ElementType item, int Tag)
{
/*Tag作为区分两个堆栈的标志，取值为1/2*/
if (ptrs->top2-ptrs->top1==)
{
printf("栈满！"); return;
}
if (Tag==)
{
ptrs->Data[++(ptrs->top1)] = item;
}
else
{
ptrs->Data[--(ptrs->top2)] = item;
}
} ElementType Pop(struct DStack *ptrs,int Tag)
{
if (Tag==)
{
if (ptrs->top1==-)
{
printf("栈1空！");
return NULL;
}
else
{
return ptrs->Data[(ptrs->top1)--];
}
}
else
{
if (ptrs->top2==MAXSIVE)
{
printf("栈2空！");
return NULL;
}
else
{
return ptrs->Data[(ptrs->top2)++];
}
}
} int main()
{
//struct DStack *S=(DStack_)malloc(sizeof(struct DStack));
struct DStack stack;
DStack_ S = &stack;
S->top1 = -;
S->top2 = MAXSIVE; for (int i = ; i < ;i++)
{
Push(S, i, );
Push(S, - i, );
} for (int i = ; i <= S->top1;i++)
{
printf("%d ",S->Data[i]);
}
printf("\n");
for (int i = MAXSIVE-; i >= S->top2; i--)
{
printf("%d ", S->Data[i]);
}
printf("\n");
return ;
}
![2023-08-10：景区里有m个项目，也就是项目数组为int[][] game，这是一个m*2的二维数组 景区的第i个项目有如下两个参数： game[i] = { Ki, Bi } Ki一定是负数，](https://www.kunjuke.com/file/css/thumb/11.jpg/280-180.jpg)