从零开始算法之路 ---- 最小栈

朱雀 2021-11-10 13:14 446阅读 0赞

###### 这篇博客虽然简单、垃圾，但本来就是我自己写的，没有参考过别的博客 ，原文链接就是本篇地址，不要见怪。我这么写是 CSDN 评审不过，非说我不是原创。 ######

**前言**:小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）  
**题源:** 力扣(LeetCode）[https://leetcode-cn.com/problems/min-stack][https_leetcode-cn.com_problems_min-stack]  
**题目描述:**  
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) – 将元素 x 推入栈中。  
  pop() – 删除栈顶的元素。  
  top() – 获取栈顶元素。  
  getMin() – 检索栈中的最小元素。  
**示例:**

MinStack minStack = new MinStack();  
  minStack.push(-2);  
  minStack.push(0);  
  minStack.push(-3);  
  minStack.getMin(); --> 返回 -3.  
  minStack.pop();  
  minStack.top(); --> 返回 0.  
  minStack.getMin(); --> 返回 -2.  
**思路:顺序栈（用一位数组实现）** 详情看代码。  
**代码：**

class MinStack { 
            private:
            // 定义栈顶指针
            int topp;
            // 定义栈能存储最多元素个数
            int maxSize;
            // 定义顺序栈，用一维数组实现
            int *elements;
        
        public:
                  
            /** initialize your data structure here. */
            MinStack() { 
                // 定义一个构造函数初始化书需个变量
                // 初始化栈顶指针 topp = -1, 表示栈为空
                topp = -1;
                // 假设改栈能存储的最大元素个数为 200
                //maxSize = 500; 稍微大一点，如果用 500 会出错
                maxSize = 1000;
                // 初始化栈空间
                elements = new int[maxSize];
    
            }
            // 将元素 x 推入栈中。
            void push(int x) { 
                // 先判断栈满否，满则元素不能进栈，返回结束
                if(topp == maxSize - 1) return;
                // 栈不满，元素进栈，栈顶指针先加 1 再进栈
                topp = topp + 1;
                elements[topp] = x;
            }
            // 删除栈顶的元素。
            void pop() { 
                // 先判断栈是否为空，为空则没有元素可删除，返回结束
                //if(topp == -1) return ;
                // 如果栈不为空，则删除栈顶元素,栈顶指针减 1 
                topp = topp - 1;
            }
            // 获取栈顶元素。
            int top() { 
                // 先判断栈是否为空，为空则没有元素可获取，返回结束
                //if(topp == -1) return 0;
                // 如果栈不为空，返回栈顶元素
                if(topp == -1) return NULL;
                return elements[topp];
    
            }
    
            int getMin(){ 
                // O(n) 的时间复杂度
                if(topp == -1) return NULL;
                int min = elements[0];
                for(int i = 1; i <= topp; i++){ 
                    if(min > elements[i])
                        min = elements[i];
                }
                return min;
            }
    };

[https_leetcode-cn.com_problems_min-stack]: https://leetcode-cn.com/problems/min-stack