江月迟迟的个人知识库

外观

单调栈 ​

作者:江月迟迟
发表于:2024-12-30
字数统计:2469 字
预计阅读9分钟

概论 ​

单调栈是用来遍历数组时，按单调递增规则或者单调递减规则处理辅助栈，因为辅助栈是单调的，所以叫做单调栈。

我们定义：

  • 单调递增栈：只有比栈顶元素小的元素才能直接进栈，否则需要先将栈中比当前元素小的元素出栈，再将当前元素入栈。这样就保证了：栈中保留的都是比当前入栈元素大的值，并且从栈顶到栈底的元素值是单调递增的。
  • 单调递减栈：只有比栈顶元素大的元素才能直接进栈，否则需要先将栈中比当前元素大的元素出栈，再将当前元素入栈。这样就保证了：栈中保留的都是比当前入栈元素小的值，并且从栈顶到栈底的元素值是单调递减的。

实际定义起来各有说法，明晰之后是：维护辅助栈单调递增，那么栈内的元素是单调递减的，维护辅助栈单调递减，那么栈内的元素是单调递增的。下文，我提到单调递增栈，即是维护辅助栈单调递增的意思。

单调栈需要确定两个问题，第一，辅助栈应该是单调递增还是单调递减。第二，处理数组元素时，这个元素可能大于、等于、小于辅助栈栈头元素，此时怎么处理数组元素。显然，第一个问题和第二个问题是同一个具体问题的不同描述。

关于这个问题怎么解决，一般来说，看题目需要比较的信息，比如739. 每日温度中给定一个数组，需要知道数组每个元素的下一个更高温度（元素）出现在几天后，表达式即arr[i] - stack.pop()，显然stack.pop()是一个小的元素，那么需要维护单调栈单调递增（请注意定义）。比如496. 下一个更大元素 I中，也是求数组右边第一个大的，同理也是维护单调栈单调递增。比如42. 接雨水中，即是求元素右边第一个大的（因为遇到小的要记录凹槽低多少，一直到找到右边第一个大的），即是维护单调栈单调递增。比如84. 柱状图中最大的矩形，要找到数组右边第一个小的（因为矛盾是拓展的长度和右边第一个小的与之前的左边的损耗，表达式ans = Math.max(ans, len * right)）体现出一种贪心的思想，所以是维护单调栈单调递减。

另外，单调栈记录的内容也需要确定，一般来说，记录的是数组下标，因为知道数组下标后，很便利找到对应数组元素，但是如果记录数组元素，那么会丢失下标信息，导致题目做不出来（你也不想做着做着回过头改辅助栈内容吧）

在技巧上，有时会记录头与之前的(0元素、空元素)，以及尾与之后的（0元素、空元素）的比较，所以有需要时，往源数组中插入头先0和尾后0。

模板 ​

单调递减 ​

js
var MonotoneStack = function(arr) {
    // 初始化
    let result = 0
    const st = []
    // 决定要不要记录头前0和尾后0
    st.push(0)
    arr.unshift(0)
    arr.push(0)
    // 主要逻辑：维护单调栈（这里是单调递减）
    for(let i = 1; i < arr.length; i++) {
        // 维护单调栈单调递减，即是维护从栈头到栈底单调递减，即是遇到数组元素比栈头大时，推入该数组元素
        // 经过简化后，规则为：数组元素比栈头小时，把元素都弹出，那么再推入数组元素时，就一定比栈头大了。
        while(arr[i] < arr[st[st.length-1]]) {
            // 弹出和记录答案的逻辑
            let mid = st.pop()
            let w = i - st[st.length-1] - 1
            let h = arr[mid]
            result = Math.max(result, w * h)
        }
        st.push(i)
    }
    return result
};

单调递增 ​

js
var dailyTemperatures = function(temperatures) {
    // 这里需要单调栈，存放的元素是下标
    // 初始化过程
    const st = [], result = Array(temperatures.length).fill(0)
    // st推入0，决定数组元素是否要先导0和尾后0
    st.push(0)
    for(let i = 1; i < temperatures.length; i++) {
        // 维护单调栈单调递增，即是维护单调栈从栈头到栈底单调递增，就是数组元素比栈头小时，推入该数组元素
        // 经过化简后，在数组元素大于栈头元素时，疯狂弹出，这样后面再推入就一定符合上一条规则了
        while(temperatures[st[st.length-1]] < temperatures[i] && st.length) {
            result[st[st.length-1]] = i - st[st.length-1]
            st.pop() 
        }
        st.push(i)
    }
    return result
};

题单 ​

739. 每日温度 ​

js
/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    // 这里需要单调栈，存放的元素是下标
    const result = Array(temperatures.length).fill(0), st = []
    st.push(0)
    for(let i = 1; i < temperatures.length; i++) {
        if(temperatures[i] > temperatures[getStackTop(st)]) {
           while(st.length && temperatures[i] > temperatures[getStackTop(st)]) {
                const pop = st.pop()
                result[pop] = i - pop
           }
        }
        st.push(i)
    }

    return result

    function getStackTop(st) {
        return st[st.length-1]
    }
};


var dailyTemperatures = function(temperatures) {
    // 这里需要单调栈，存放的元素是下标
    const st = [], result = Array(temperatures.length).fill(0)
    st.push(0)
    for(let i = 1; i < temperatures.length; i++) {
        // 维护单调栈单调递增
        while(temperatures[st[st.length-1]] < temperatures[i] && st.length) {
            result[st[st.length-1]] = i - st[st.length-1]
            st.pop() 
        }
        st.push(i)
    }
    return result
};

496. 下一个更大元素 I ​

js
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    const result = []
    const result2 = Array(nums2.length).fill(-1)
    const st = []
    st.push(0)
    for(let i = 1; i < nums2.length; i++) {
        while(st.length && nums2[i] > nums2[st[st.length-1]]) {
            const pop = st.pop()
            result2[pop] = nums2[i]
        }
        st.push(i)
    }
    nums1.forEach(n1 => {
        result.push(result2[nums2.indexOf(n1)])
    })
    return result
};

503. 下一个更大元素 II ​

js
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var nextGreaterElements = function(nums) {
    const doubleNums = nums.concat(nums)
    const result = Array(nums.length).fill(-1)
    const st = []
    st.push(0)
    for(let i = 1, j = i; i < doubleNums.length; i++) {
        while(st.length && doubleNums[i] > doubleNums[st[st.length-1]]) {
            result[st.pop()] = doubleNums[i]
        }
        st.push(i)
    }
    return result.slice(0, nums.length)
};

42. 接雨水 ​

js
//暴力解法
var trap = function(height) {
    const len = height.length;
    let sum = 0;
    for(let i = 0; i < len; i++){
        // 第一个柱子和最后一个柱子不接雨水
        if(i == 0 || i == len - 1) continue;
        let rHeight = height[i]; // 记录右边柱子的最高高度
        let lHeight = height[i]; // 记录左边柱子的最高高度
        for(let r = i + 1; r < len; r++){
            if(height[r] > rHeight) rHeight = height[r];
        }
        for(let l = i - 1; l >= 0; l--){
            if(height[l] > lHeight) lHeight = height[l];
        }
        let h = Math.min(lHeight, rHeight) - height[i];
        if(h > 0) sum += h;
    }
    return sum;
};

//双指针
var trap = function(height) {
    const len = height.length;
    if(len <= 2) return 0;
    const maxLeft = new Array(len).fill(0);
    const maxRight = new Array(len).fill(0);
    // 记录每个柱子左边柱子最大高度
    maxLeft[0] = height[0];
    for(let i = 1; i < len; i++){
        maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);
    }
    // 记录每个柱子右边柱子最大高度
    maxRight[len - 1] = height[len - 1];
    for(let i = len - 2; i >= 0; i--){
        maxRight[i] = Math.max(height[i], maxRight[i + 1]);
    }
    // 求和
    let sum = 0;
    for(let i = 0; i < len; i++){
        let count = Math.min(maxLeft[i], maxRight[i]) - height[i];
        if(count > 0) sum += count;
    }
    return sum;
};

//单调栈 js数组作为栈
var trap = function(height) {
    const len = height.length;
    if(len <= 2) return 0; // 可以不加
    const st = [];// 存着下标，计算的时候用下标对应的柱子高度
    st.push(0);
    let sum = 0;
    for(let i = 1; i < len; i++){
        if(height[i] < height[st[st.length - 1]]){ // 情况一
            st.push(i);
        }
        if (height[i] == height[st[st.length - 1]]) {  // 情况二
            st.pop(); // 其实这一句可以不加，效果是一样的，但处理相同的情况的思路却变了。
            st.push(i);
        } else { // 情况三
            while (st.length !== 0 && height[i] > height[st[st.length - 1]]) { // 注意这里是while
                let mid = st[st.length - 1];
                st.pop();
                if (st.length !== 0) {
                    let h = Math.min(height[st[st.length - 1]], height[i]) - height[mid];
                    let w = i - st[st.length - 1] - 1; // 注意减一，只求中间宽度
                    sum += h * w;
                }
            }
            st.push(i);
        }
    }
    return sum;
};

//单调栈 简洁版本 只处理情况三
var trap = function(height) {
    const len = height.length;
    if(len <= 2) return 0; // 可以不加
    const st = [];// 存着下标，计算的时候用下标对应的柱子高度
    st.push(0);
    let sum = 0;
    for(let i = 1; i < len; i++){ // 只处理的情况三，其实是把情况一和情况二融合了
        while (st.length !== 0 && height[i] > height[st[st.length - 1]]) { // 注意这里是while
            let mid = st[st.length - 1];
            st.pop();
            if (st.length !== 0) {
                let h = Math.min(height[st[st.length - 1]], height[i]) - height[mid];
                let w = i - st[st.length - 1] - 1; // 注意减一，只求中间宽度
                sum += h * w;
            }
        }
        st.push(i);
    }
    return sum;
};

// 双指针2
var trap = function(height) {
    let ans = 0, left = 0, right = height.length - 1, preMax = 0, sufMax = 0
    while(left < right) {
        preMax = Math.max(preMax, height[left])
        sufMax = Math.max(sufMax, height[right])
        if(preMax < sufMax) {
            ans += preMax - height[left]
            left++
        } else {
            ans += sufMax - height[right]
            right--
        }
    }
    return ans
}

84. 柱状图中最大的矩形 ​

js
/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    let result = 0
    const st = []
    st.push(0)
    heights.unshift(0)
    heights.push(0)
    for(let i = 1; i < heights.length; i++) {
        while(heights[i] < heights[st[st.length-1]]) {
            let mid = st.pop()
            let w = i - st[st.length-1] - 1
            let h = heights[mid]
            result = Math.max(result, w * h)
        }
        st.push(i)
    }
    return result
};


var largestRectangleArea = function(heights) {
    // 使用单调栈解决这个问题
    const st = []
    let result = 0
    st.push(0)
    heights.push(0)
    heights.unshift(0)
    for(let i = 1; i < heights.length; i++) {
        // 维护单调栈单调递增，否则计算答案
        if(heights[st[st.length-1]] > heights[i]) {
            while(heights[st[st.length-1]] > heights[i] && st.length) {
                const node = st.pop()
                const height = heights[node]
                const width = i - st[st.length-1] -1
                result = Math.max(result, height * width)
            }
            st.push(i)
        } else {
            st.push(i)
        }
    }
    return result
};