首页 > C++的STL栈实现获取栈中最小元素的成员

C++的STL栈实现获取栈中最小元素的成员

实现一个获取栈中最小数据成员的函数，该栈支持如下操作：

1.push(x) : 将元素x压入栈中

2.pop() : 弹出(移除)栈顶元素

3.top() : 返回栈顶元素

4.getMin() : 返回栈内最小元素

要求时间复杂度为O(1)

这里关键是如何获取最小值，栈中的元素不断增加，且要达到O（1）常数级的时间复杂度，即创建好的栈进行排序，返回最小值是不可行的。

这里只有在创建过程中将栈中的最小值获取到，此时一个可行的办法为：

维护一个最小栈，保持栈顶元素为所有元素的最小值，且大小与原本数据栈保持一致。

这样即使有原本数据的删除添加，最小栈同样跟随数据删除添加即可。

在这里插入图片描述

方法一（一个栈）：

数据结构实现如下:

void push(int x) { data_stack.push(x);/*当最小栈中的元素不为空的时候，和栈顶元素进行大小比较，判断是否要入栈*/if (!min_stack.empty()) { if (min_stack.top() > x) { min_stack.push(x);}else { min_stack.push(min_stack.top());}}/*为空的时候即可入栈*/else { min_stack.push(x);}
}
/*此时最小栈的栈顶即为数据栈中的最小元素*/
int get_min(){ return min_stack.top();
}

方法二（两个栈）：

class MinStack { stack<int> S;int min=2147483647;
public:/** initialize your data structure here. */MinStack() { }//push操作void push(int x) { if (x <= min) {  //当遇到小于等于最小值的数值，将上一个最小值也push到栈中S.push(min);min = x;}S.push(x);}void pop() { if (S.top() == min) {  //pop的时候发现pop的时最小值，那么pop两次，同时变更最小值S.pop();min = S.top();S.pop();} else { S.pop();}}int top() { return S.top();}int getMin() { return min;}
};

测试代码实现如下:

#include 
#include 
#include using namespace std;class My_stack{ private:stack<int> data_stack,min_stack;public:void push(int x) { data_stack.push(x);if (!min_stack.empty()) { if (min_stack.top() > x) { min_stack.push(x);}else { min_stack.push(min_stack.top());}}else { min_stack.push(x);}}void pop() { min_stack.pop();data_stack.pop();}int top() { return data_stack.top();}int get_min(){ return min_stack.top();}
};int main(){ My_stack s;int tmp;cout << "construct the stack " << endl;while(cin >> tmp) { s.push(tmp);}cout << "min is " << s.get_min() << endl;s.pop();cout << "after pop " << s.top() << endl;s.push(-4);cout << "after push ,the top and min is " << s.top() << " " << s.get_min() << endl;return 0;
}

输出如下:

construct the stack 
2 -1 -3 2 0 4
d
min is -3
after pop 0
after push -4,the top and min is -4 -4

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • C++ Stack Queue priority_queue

    栈stack：stack 后入先出（LIFO） q.top()获取栈顶元素（并不删除）q.pop()删除栈顶元素q.push(x)向栈中加入元素q.empty()判断栈是否为空 队列queue：先入先出（FIFO）   q.front()获取队首元素（并不删除）q.pop()删除队首元素q.push(x)向队列中加入元素q....

  • c++ resizereserve

    resize()，设置大小（size）; reserve()，设置容量（capacity）; size()是分配容器的内存大小，而capacity()只是设置容器容量大小，但并没有真正分配内存。 打个比方：正在建造的一辆公交车，车里面可以设置40个座椅（reserve(40);），这是它的容量，但并不是说它里面就有了40个座椅，只能说...

  • 用v-for循环动态定位坐标显示元素，并遍历元素的left和top坐标位置（只需要用到元素的宽高、索引、每行显示数量）

    v-for="(index,$i) in total" :key="$i":style="{left:`${itemWidth*((index-1)%rowItemCount)}px`,top:`${itemHeight*(Math.ceil(index/rowItemCount)-1)}px`}" //total是显示总数量 //l...

  • 几种经典的居中技巧（垂直和水平居中）

      技巧一（推荐指数★★★★★） 采用top、right、bottom、left，可以不在乎父元素的宽度和高度，对GPU损耗低于技巧三，但是对浏览器内存的消耗高于技巧三 .子元素 {/*父元素需要position: relative|absolute;*/position: absolute;margin: auto;to...

  • leetcode-155 最小栈

    设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。pop() – 删除栈顶的元素。top() – 获取栈顶元素。getMin() – 检索栈中的最小元素。 示例： MinStack minStack = new MinStack(); minStack...

©2024 11GX.COM