算法-单调栈

首先要弄清楚单调栈问题用来解决什么，还有常规的写法。

用来解决什么？

一般用来解决找出数组中某个元素的下一个更大/更小元素这一类问题。

常规写法是怎么样的？

var fn = function (nums) {
    let res = new Array(nums.length).fill(0);
    // stack存储的是数组的下标
    let stack = [0];

    for (let i = 1; i < n; i++) {
        // 新元素大于栈顶元素 入栈
        while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
            let index = stack.pop();
            // ...进行具体处理
        }
        stack.push(i);
    }

    return res;
};

1. leetcode739 每日温度

这题要求下一个更高温度出现在几天后，那么在进行具体处理那块进行差值计算即可：

var dailyTemperatures = function (temperatures) {
    let n = temperatures.length;
    let res = new Array(n).fill(0);
    // 存储temeratures中的下标
    let stack = [0];

    for (let i = 1; i < n; i++) {
        // 新元素大于栈顶元素 入栈 将小的元素挤出去并计算天数差值
        while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            let index = stack.pop();
            res[index] = i - index;
        }
        stack.push(i);
    }

    return res;
};

2. leetcode496 下一个更大元素Ⅰ

这题相比上一题难点在于引入了另一个数组，因此需要用到map来存储nums2中找到的“下一个更大元素”的映射关系，然后再回到nums1中去使用映射关系。

var nextGreaterElement = function(nums1, nums2) {
    // stack里存的是nums2元素的下标
    let stack = [0], res = [];
    let map = new Map();

    for(let i = 1 ; i < nums2.length ; i++) {
        while(stack.length && nums2[i] > nums2[stack[stack.length - 1]]) {
            let index = stack.pop();
            // 设置nums2中第一个比index大的元素
            map.set(nums2[index], nums2[i]);
        }
        stack.push(i);
    }

    // 回到nums1中根据map寻找下一个更大元素
    for(let i = 0 ; i < nums1.length ; i++) {
        res[i] = map.get(nums1[i]) || -1;
    }

    return res;
};

3. leetcode503 下一个更大元素Ⅱ

这题引入了循环数组，因此稍作调整，将遍历长度修改为数组长度的两倍，同时对i进行取余即可。

别的内容和每日温度基本都是一样的，就是进行具体处理时，每日温度的res[index]存的是差值，这题的res[index]存的是元素本身。

var nextGreaterElements = function(nums) {
    let n = nums.length;
    let res = new Array(n).fill(-1), stack = [0];

    for(let i = 1 ; i < n * 2 ; i++) {
        while(stack.length && nums[i % n] > nums[stack[stack.length - 1]]) {
            let index = stack.pop();
            res[index] = nums[i % n];
        }
        stack.push(i % n);
    }

    return res;
};

leetcode42 接雨水

这题大致模板还是和前面的一样，难点在于具体的逻辑处理，怎么去计算接到的雨水的面积？

根据这张图分析，就会变得比较清晰：

• 栈顶元素为mid，也就是凹槽部分
• 左边界为栈顶元素的左边第一个元素
• 右边界为当前遍历的元素

这样的话就能够写出以下代码：

var trap = function(height) {
    // stack中存储的是height数组的下标
    let stack = [0], res = 0;

    for(let i = 1 ; i < height.length ; i++) {
        while(stack.length && height[i] > height[stack[stack.length - 1]]) {
            // 逻辑处理部分 首先取中间元素
            let mid = stack.pop();
            // 随后取左右边界元素
            if(stack.length) {
                let h = Math.min(height[stack[stack.length - 1]], height[i]) - height[mid];
                let w = i - stack[stack.length - 1] - 1;
                res += h * w;
            }
        }
        stack.push(i);
    }

    return res;
};

要注意这种计算方法是按照行来计算雨水面积，注意区分和按列计算的区别：