当前位置:   article > 正文

数据结构之栈总结_数据结构栈的心得体会

数据结构栈的心得体会

一、介绍

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
在这里插入图片描述

二、有关栈的算法

(1)最小栈

最小栈主要用来记录栈中最小元素,方便O(1)复杂度获取。
算法思想:定义两个栈,一个栈正常的弹出和推进,另一个栈的栈顶保持当前正常栈的最小值。
力扣155—最小栈来讲解。
1、定义两个栈:

var MinStack = function() {
    this.stack = []
    this.minStack = [Infinity]
};
  • 1
  • 2
  • 3
  • 4

2、写push方法,stack正常推入元素,minStack每次推入都要和当前栈顶比较,若当前元素小于栈顶元素的话,则推入,否则继续推入当前栈顶元素。(原因:保持minStack的栈顶一直都是stack的最小值)

MinStack.prototype.push = function(val) {
    this.stack.push(val)
    this.minStack.push(Math.min(val,this.minStack[this.minStack.length - 1]))
};
  • 1
  • 2
  • 3
  • 4

3、写pop方法,两个栈都一起pop,因为如果只有stack pop的话,minStack就不能保持它的栈顶是stack的最小值了。

MinStack.prototype.pop = function() {
    this.stack.pop()
    this.minStack.pop()
};
  • 1
  • 2
  • 3
  • 4

4、取栈顶即stack中的栈顶元素。

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1]
};
  • 1
  • 2
  • 3

5、取最小值即minStack的栈顶元素。

MinStack.prototype.getMin = function() {
    return this.minStack[this.minStack.length - 1]
}
  • 1
  • 2
  • 3

(2)单调栈

单调栈适用于对序列中每个元素,寻找离当前元素左边最近最小(大)的,右边最近最小(大)的。
算法思想:

  1. 初始化一个空栈
  2. 对目标数组元素进行循环
  3. 判断栈是否为空且当前元素比下标为栈顶元素的目标数组元素大(小)(因为栈中存的是数组下标),不为空且比当前元素大的话(假设寻找下一个最大,那栈顶到栈底的顺序是从小到大),进行记录,栈顶元素所对应的数值左边最近最大的为栈顶元素的下一个元素,右边最近最大的为当前元素,然后将栈顶元素出栈。不满足以上两个条件的话,将当前元素进栈。(这样栈里的元素才能保持从小到大的)。

核心代码:

// 核心代码(找下一个最大(栈底->栈顶:大 -> 小))
for(let i = 0; i < nums2.length; i++){
    let num = nums2[i]
    while(stack.length !== 0 && num > nums2[stack[stack.length - 1]]){
        map.set(stack[stack.length - 1],i)
        stack.pop()
        // stack.push(i)
    }
    stack.push(i)
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

相关例题有:
1.力扣496—下一个更大元素I
解法1:暴力解法

var nextGreaterElement = function (nums1, nums2) {
    // 暴力解法
     let n = nums1.length
     let m = nums2.length
     let res = new Array(n).fill(0)

     for (let i = 0; i < n; i++) {
         let j = 0;
         while (j < m && nums1[i] !== nums2[j]) {
             j++
         }
         let k = j + 1
         while (k < m && nums2[k] < nums2[j]) {
             k++
         }
         res[i] = k < m ? nums2[k] : -1

     }
     return res
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

解法2:单调栈 + Map

var nextGreaterElement = function (nums1, nums2) {
 	// 单调栈
    let stack = []
    let res = []
    let map = new Map()
    for(let i = 0; i < nums2.length; i++){
        let num = nums2[i]
        while(stack.length !== 0 && num > nums2[stack[stack.length - 1]]){
            map.set(stack[stack.length - 1],i)
            stack.pop()
            // stack.push(i)
        }
        stack.push(i)
    }
    console.log(map)
    for(let i = 0; i < nums1.length; i++){
        let key = nums2.indexOf(nums1[i])
        console.log(key)
        if(!map.get(key)){
            res.push(-1)
        }else{
            res.push(nums2[map.get(key)])
        }
    }
    return res
}
  • 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

2.力扣503—下一个更大元素II
解法类似,只是题目说的是循环数组,其实把该数组循环次数改为2*n-1次即可。(因为是自己找自己,寻找下标已经确定好了,所以就不需要map记录了)。

var nextGreaterElements = function(nums) {
    let stack = []
    let map = new Map()
    let n = nums.length
    let res = new Array(n).fill(-1)
    
    for(let i = 0; i < 2 * n - 1; i++){
        let num = nums[i % n]
        while(stack.length !== 0 && num > nums[stack[stack.length - 1]]){
            res[stack[stack.length - 1]] = num
            stack.pop()
        }
        stack.push(i % n)
    }
    return res
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

三、其他关于栈的题型

1.力扣20—有效的括号
解决思路:
1.定义一个空栈
2.遍历字符串,若当前元素为左括号,就将其入栈。否则取栈顶(注意:不是出栈),判断当前元素与栈顶元素是否是一对的,如果是一对的话,就将栈顶元素出栈,否则直接返回false。
3.最后检查栈是否为空,若为空,返回true,否则返回false。

var isValid = function(s) {
    let stack = []
    for(let i = 0; i < s.length; i++){
        let str = s[i]
        if(str === '(' || str === '{' || str === '['){
            stack.push(str)
        }else{
            let start = stack[stack.length - 1]
            if((start === "(" && str === ')') || (start === "{" && str == '}') || (start == '[' && str == ']')){
                stack.pop()
            }else{
                return false
            }
        }
    }
    return stack.length == 0 ? true : false
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

2.力扣71—简化路径
思路:
1.对字符串根据“/”分割,得到一个拥有所有文件名的数组。
2.遍历分割后的数组,判断当前元素是否为空或为“.”,表示在当前目录下,直接continue,不用将其处理
3.若为“…”,表示在上一层目录中,将栈顶元素出栈
4.否则,将当前元素压入栈中
5.最后使用“/”将栈中的元素拼接起来,在最前面加个“/”,表示在当前目录下。

var simplifyPath = function (path) {
    let stack = []
    let arr = path.split('/')
    for (let i = 0; i < arr.length; i++) {
        let val = arr[i]
        if (val == '' || val === '.') {
            continue
        } else if (val === '..') {
            stack.pop()
        } else {
            stack.push(val)
        }
    }

    return '/' + stack.join('/')
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/一键难忘520/article/detail/896711
推荐阅读
相关标签
  

闽ICP备14008679号