Skip to content

Latest commit

 

History

History
154 lines (120 loc) · 5.31 KB

2.1.3.md

File metadata and controls

154 lines (120 loc) · 5.31 KB
Raw

贰.1.3 单调栈

贰.1.3.1 定义

单调栈，顾名思义就是栈内元素单调按照递增(递减)顺序排列的栈。这里的单调递增或递减是指的从栈顶到栈底单调递增或递减。

示例：用数组[7,4,9,5,3,2]构建一个单调递增栈。

代码示例：

(()=>{
    let A=[7,4,9,5,3,2],stk=[];
    let l=A.length;
    for (let i = 0; i < l; i++) {
        while (stk.lenght && A[i] > A[stk[stk.length-1]]) { // 单调递增栈
            // 单调递减栈的情况为 A[i] < A[stk[stk.length-1]]]
            stk.pop();
        }
        stk.push(i);
    }
})();

贰.1.3.2 应用场景

  • 找出数组中每项左/右边第一个大于/小于它的解；
  • 题目中隐含查找第一个（或离此项元素最近的）大于/小于此项元素的值，这类问题都可以考虑用单调栈求解。

贰.1.3.3 应用示例

1.气温问题（LeetCode.739）

题目如下：

根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个数组T= [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是[1, 1, 4, 2, 1, 1, 0, 0]。

解法一

这道题用若2个暴力循环的办法解决，时间复杂度是 $$O(N^2)$$ ；

/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function (T) {
    let arr = [];
    let l = T.length;

    for (let i = 0; i < l; i++) {
        if (i == l - 1) {//末尾一定是0
            arr.push(0);
        } else {
            for (let j = i + 1; j < l; j++) {
                if (T[j] > T[i]) {
                    arr.push(j - i);
                    break;
                }else if(j==l-1){
                    arr.push(0);
                }
            }
        }
    }

    return arr;
};

解法二

而若使用单调栈，时间复杂度能将为 $$O(N)$$ 。来分析下这道题，思路如下：

  • 维护一个单调递增栈，栈内存储气温数组 T 的 index ；
  • 查看当前元素是否大于栈顶元素所对应的 T 的值，也就是 T[stack[stack.length - 1]] ；
  • 如果大于，那说明找到需要等待的天数。如果不大于那说明还没到找到比这天高的温度，同时继续维护这个单调栈；
  • 如果大于，需要等待的天数就是当前数组 T 的index减去单调栈顶对应的index；
  • 若循环完毕还没有找到，则需要等待的天数为0。
/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function(T) {
    let { length } = T;
    let res = new Array(length).fill(0);
    let stack = [];
    for(let i = 0; i < length; i++) {
        while(stack.length && T[i] > T[stack[stack.length - 1]]) {
            let index = stack.pop();//条件满足得到一个结果之后，取出栈顶存放的index
                                    //并执行出栈，可以接着计算下一个了。
            res[index] = i - index;//res[index]是巧妙之处，存放天数
        }
        stack.push(i);//栈内存放T的index
    }
    return res;
};

说白了就是空间换时间，新增一个单调栈存放index，巧妙地来换取时间复杂度的降低。

2.求数组项左右两侧比该项小的第一个数

原题如下：

给定一个长度为N的正整数数组，输出每个数组项左右两边第一个比它小的数，如果不存在则输出 - 1。

输入： [3, 4, 2, 7, 5]

输出：
左边 [-1, 3, -1, 2, 2]
右边 [2, 2, -1, 5, -1]

解题思路：

  • 用一个单调栈存放数组项的index；
  • 用两个数组存放两侧输出结果；
  • 栈顶（对应的数组项）右边第一个更小的元素是即将入栈的当前元素；
  • 数组当前项左边的第一个更小的元素，是栈顶元素（对应的数组项）。
((arr) => {
    let l = arr.length;
    let stack = [];
    let resLeft = new Array(l).fill(-1);
    let resRight = new Array(l).fill(-1);
    
    for (let i = 0; i < l; i++) {
        while (stack.length && arr[i] < arr[stack[stack.length - 1]]) {
            let index = stack.pop();
            resRight[index] = arr[i];
            if (stack.length)
                resLeft[index] = arr[stack[stack.length - 1]];
        }
        stack.push(i);
    }
    
    console.log(resLeft, resRight);
})([3, 4, 2, 7, 5]);

贰.1.3.4 总结要点

单调栈的核心并不是单调，单调递增或者递减只不过是副产品。其实际意义在于：

  • 实际上单调栈中并不保存数组项的值，而是保存数组项在原数组中的索引位置（index），它把空间复杂度从O(1)增大为O(N)；
  • 因为针对单调栈又做了一遍历子循环（while），结合出栈操作，这个循环内可以巧妙地做很多事情；由此，单调栈成为一个临时用来协助降低时间复杂度的数据结构，；
  • 若从1到N遍历数组一遍，把每个将要放入的数组项其对应的索引位置（index）记录到栈里，就可以在O(N)的时间复杂度内得到数组所有项的左/右边、距离该项元素最近、且比该项元素大/小的其他元素的索引位置（index）。