leetcode刷题（5）

女爷i 2023-09-25 23:47 57阅读 0赞

各位朋友们，大家好，今天是我leedcode刷题的第五篇，我们一起来看看吧。

#### 文章目录 ####

*  栈的压入，弹出序列
 *   *  题目要求
     *  用例输入
     *  提示
     *  做题思路
     *  代码实现
     *   *  C语言代码实现
         *  Java代码实现
 *  最小栈
 *   *  题目要求
     *  用例输入
     *  提示
     *  做题思路
     *  代码实现
     *   *  Java代码实现

## 栈的压入，弹出序列 ##

[leetcode之栈的压入与弹出序列（难度：中等）][leetcode]

### 题目要求 ###

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 \{1,2,3,4,5\} 是某栈的压栈序列，序列 \{4,5,3,2,1\} 是该压栈序列对应的一个弹出序列，但 \{4,3,5,1,2\} 就不可能是该压栈序列的弹出序列。

### 用例输入 ###

示例 1：  
输入：pushed = \[1,2,3,4,5\], popped = \[4,5,3,2,1\]  
输出：true  
解释：我们可以按以下顺序执行：  
push(1), push(2), push(3), push(4), pop() -> 4,  
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：  
输入：pushed = \[1,2,3,4,5\], popped = \[4,3,5,1,2\]  
输出：false  
解释：1 不能在 2 之前弹出。

### 提示 ###

0 <= pushed.length == popped.length <= 1000  
0 <= pushed\[i\], popped\[i\] < 1000  
pushed 是 popped 的排列。

### 做题思路 ###

我们来分别遍历这两个数组，遍历的同时先将pushed数组压入栈中，然后我们判断栈顶的数据是否跟popped数组的数据相等，如果相等就出栈，popped数组的下标+1，不相等我们就继续将pushed数组中的数据压入栈中，循环中这个数组，最后如果栈中为空则说明popped序列是pushed数组的弹出序列，不为空则不是。  
![在这里插入图片描述][1bdd7bf56ddf4746ba23a4317bfa25a3.png]  
![在这里插入图片描述][00ba7398d9564c519836f70b24e1825d.png]

![在这里插入图片描述][fc8d73ef62ae438a8b9f3cafb5f328ee.png]  
![在这里插入图片描述][8cab94d5800349c7a4958367ca2ebf6b.png]  
此时栈顶的数据等于popped\[j\]，所以我们弹出栈顶的数据，并且将j++；  
![在这里插入图片描述][02ee0e20be154db19de81a669fa67828.png]  
![在这里插入图片描述][0ae61e92fbae4d99a8a0c4952480ae3e.png]  
栈顶数据等于popped\[j\]，继续弹出。  
![在这里插入图片描述][ac6f6255252941b2b638ea19c93d08dd.png]  
继续该操作  
![在这里插入图片描述][965a37dd925948e3b6cd390ea1807dbe.png]  
栈里面为空，所以我们返回true。

### 代码实现 ###

#### C语言代码实现 ####

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize){
        
        int* arr = (int*)malloc(pushedSize*sizeof(int));
        int tail = 0;
        int j = 0;
        for(int i = 0; i<pushedSize; i++)
        {
        
            arr[tail] = pushed[i];
            while(j<poppedSize && tail>=0 && arr[tail] == popped[j])
            {
        
                tail--;
                j++;
            }
            tail++;
        }
        return tail==0;
    }

![在这里插入图片描述][a15ae602b1f941398c844127b97af509.png]

#### Java代码实现 ####

class Solution {
        
        public boolean validateStackSequences(int[] pushed, int[] popped) {
        
            Stack<Integer> stack = new Stack<>();
            int j = 0;
            for(int i = 0; i<pushed.length; i++) {
        
                stack.push(pushed[i]);
                while( j<popped.length && !stack.empty()  && stack.peek().equals(popped[j])) {
        
                    stack.pop();
                    j++;
                }
            }
            return stack.empty();
        }
    }

![在这里插入图片描述][e2b468c354544d6c8daf634865b5fdb5.png]

## 最小栈 ##

[leetcode之最小栈（难度：中等）][leetcode 1]

### 题目要求 ###

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。  
void push(int val) 将元素val推入堆栈。  
void pop() 删除堆栈顶部的元素。  
int top() 获取堆栈顶部的元素。  
int getMin() 获取堆栈中的最小元素。

这是一幕提供的接口

class MinStack {
        
    
        public MinStack() {
        
    
        }
        
        public void push(int val) {
        
    
        }
        
        public void pop() {
        
    
        }
        
        public int top() {
        
    
        }
        
        public int getMin() {
        
    
        }
    }
    
    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(val);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.getMin();
     */

### 用例输入 ###

示例 1:

输入：  
\[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”\]  
\[\[\],\[-2\],\[0\],\[-3\],\[\],\[\],\[\],\[\]\]

输出：  
\[null,null,null,null,-3,null,0,-2\]

解释：  
MinStack minStack = new MinStack();  
minStack.push(-2);  
minStack.push(0);  
minStack.push(-3);  
minStack.getMin(); --> 返回 -3.  
minStack.pop();  
minStack.top(); --> 返回 0.  
minStack.getMin(); --> 返回 -2.

### 提示 ###

\-231 <= val <= 231 - 1  
pop、top 和 getMin 操作总是在 非空栈 上调用  
push, pop, top, and getMin最多被调用 3 \* 104 次

### 做题思路 ###

这个题目需要我们使用两个栈，一个栈用来放所有整数，一个的栈顶存放的是最小的整数，叫做最小栈。当我们入栈的时候，当第一次入栈的时候因为最小栈里面是空的，所以我们直接将数据压入栈中，后来入最小栈的时候，我们就需要判断需要入栈的这个数据是否小于最小栈栈顶的数据，如果小于或等于就入栈，否则不入栈。当我们出栈的时候我们还需要对最小栈做出变化，当我们出栈的这个数等于最小栈的栈顶的数据，我们也将最小栈栈顶的数据弹出。后面的返回栈顶的数据，跟栈中的最小值我就不多叙述了。  
![在这里插入图片描述][8c0a5cb63f6c4b45b2cc5df084acfee9.png]  
![在这里插入图片描述][1d5fcca89f3448aba177252ff96d5cbf.png]  
![在这里插入图片描述][7023d9b449f44d2695840e2f207da9f8.png]  
![在这里插入图片描述][fef2f43534d14618a1241561e8994781.png]  
![在这里插入图片描述][4f1a9b17360a44a19cc23a5ca11ef879.png]  
重复此操作  
![在这里插入图片描述][422067dbed9e40989a9a22687ab4605f.png]  
然后我们在弹出三次栈

弹出的7不等于MinStack栈顶的-1  
![在这里插入图片描述][14de4345ffb7411091083527f297b39b.png]  
\-1等于MinStack栈顶的-1，所以MinStack也需要弹出  
![在这里插入图片描述][8282e4a61c044360a456cd207aff36ee.png]

![在这里插入图片描述][1428fe74003d4f7a966d93cbe721cac5.png]

### 代码实现 ###

因为这道题用C语言实现较复杂，所以我们这个题就直接用Java来实现。

#### Java代码实现 ####

class MinStack {
        
    
        private Stack<Integer> stack;
        private Stack<Integer> minstack;
        public MinStack() {
        
            stack = new Stack<>();
            minstack = new Stack<>();
        }
    
        public void push(int val) {
        
            stack.push(val);
            if(minstack.empty()) {
        
                minstack.push(val);
            } else {
        
                if(val <= minstack.peek()) {
        
                    minstack.push(val);
                }
            }
        }
    
        public void pop() {
        
        //判断栈是否为空
            if(!stack.empty()) {
        
            这里我们用Integer防止取出的数据不在-128~127之间
                Integer val = stack.peek();
                stack.pop();
                if(val.equals(minstack.peek())) {
        
                    minstack.pop();
                }
            }
        }
    
        public int top() {
        
            if(!stack.empty()) {
        
                return stack.peek();
            }
            return -1;
        }
    
        public int getMin() {
        
            if(!minstack.empty()) {
        
                return minstack.peek();
            }
            return -1;
        }
    }
    
    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(val);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.getMin();
     */

![!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/68c1b0bcc5eb4a3aa488846e7d16af76.pn][https_img-blog.csdnimg.cn_68c1b0bcc5eb4a3aa488846e7d16af76.pn]

[leetcode]: https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
[1bdd7bf56ddf4746ba23a4317bfa25a3.png]: https://img-blog.csdnimg.cn/1bdd7bf56ddf4746ba23a4317bfa25a3.png
[00ba7398d9564c519836f70b24e1825d.png]: https://img-blog.csdnimg.cn/00ba7398d9564c519836f70b24e1825d.png
[fc8d73ef62ae438a8b9f3cafb5f328ee.png]: https://img-blog.csdnimg.cn/fc8d73ef62ae438a8b9f3cafb5f328ee.png
[8cab94d5800349c7a4958367ca2ebf6b.png]: https://img-blog.csdnimg.cn/8cab94d5800349c7a4958367ca2ebf6b.png
[02ee0e20be154db19de81a669fa67828.png]: https://img-blog.csdnimg.cn/02ee0e20be154db19de81a669fa67828.png
[0ae61e92fbae4d99a8a0c4952480ae3e.png]: https://img-blog.csdnimg.cn/0ae61e92fbae4d99a8a0c4952480ae3e.png
[ac6f6255252941b2b638ea19c93d08dd.png]: https://img-blog.csdnimg.cn/ac6f6255252941b2b638ea19c93d08dd.png
[965a37dd925948e3b6cd390ea1807dbe.png]: https://img-blog.csdnimg.cn/965a37dd925948e3b6cd390ea1807dbe.png
[a15ae602b1f941398c844127b97af509.png]: https://img-blog.csdnimg.cn/a15ae602b1f941398c844127b97af509.png
[e2b468c354544d6c8daf634865b5fdb5.png]: https://img-blog.csdnimg.cn/e2b468c354544d6c8daf634865b5fdb5.png
[leetcode 1]: https://leetcode.cn/problems/min-stack/
[8c0a5cb63f6c4b45b2cc5df084acfee9.png]: https://img-blog.csdnimg.cn/8c0a5cb63f6c4b45b2cc5df084acfee9.png
[1d5fcca89f3448aba177252ff96d5cbf.png]: https://img-blog.csdnimg.cn/1d5fcca89f3448aba177252ff96d5cbf.png
[7023d9b449f44d2695840e2f207da9f8.png]: https://img-blog.csdnimg.cn/7023d9b449f44d2695840e2f207da9f8.png
[fef2f43534d14618a1241561e8994781.png]: https://img-blog.csdnimg.cn/fef2f43534d14618a1241561e8994781.png
[4f1a9b17360a44a19cc23a5ca11ef879.png]: https://img-blog.csdnimg.cn/4f1a9b17360a44a19cc23a5ca11ef879.png
[422067dbed9e40989a9a22687ab4605f.png]: https://img-blog.csdnimg.cn/422067dbed9e40989a9a22687ab4605f.png
[14de4345ffb7411091083527f297b39b.png]: https://img-blog.csdnimg.cn/14de4345ffb7411091083527f297b39b.png
[8282e4a61c044360a456cd207aff36ee.png]: https://img-blog.csdnimg.cn/8282e4a61c044360a456cd207aff36ee.png
[1428fe74003d4f7a966d93cbe721cac5.png]: https://img-blog.csdnimg.cn/1428fe74003d4f7a966d93cbe721cac5.png
[https_img-blog.csdnimg.cn_68c1b0bcc5eb4a3aa488846e7d16af76.pn]: https://img-blog.csdnimg.cn/54ec3a7e099047efb8c4600ca94bf110.png