单调栈结构解决三道算法题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：单调栈结构解决三道算法题

评论礼仪 见这里，违者直接拉黑。

[taoweidong]

000

[fornobugworld]

最后一题好像还包含一个小技巧，res会被刷新一遍，太妙了。。

[zhangmuwuge]

必须刷新 不刷新就不对了

[CNS1mple]

倒着写不是多此一举吗？

[shiboys]

明显倒着写符合向后查找比当前元素大的单调栈的特点呀

[5Reeson]

第一题文章里只给了一个模板，没有给出对应原题的题解，如果不仔细看原题，只看文章的话，可能会感觉比较困惑，建议做的时候细品原题题干～
给一个labuladong思路的 JS版本

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    let hash = new Map()
    let res = new Array(nums1.length)
    let stack = []
    for(let i = nums2.length-1;i>=0;i--){
        while(stack.length && stack[stack.length-1] <= nums2[i]){
            stack.pop()
        }
        // 栈内有元素，“下一个更大元素”为栈内元素
        if(stack.length)
            hash.set(nums2[i],stack[stack.length-1])
        // 否则，设置为-1
        else
            hash.set(nums2[i],-1)
        
        stack.push(nums2[i])
    }
    // 遍历nums1，从 hashMap 中找到对应的数
    for(let i = 0;i<nums1.length;i++){
        res[i] = hash.get(nums1[i])
    }
    return res
};

[lzh2580]

Java版本

 public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // map 映射 nums2的value 与 更大元素
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack();
        for(int i = nums2.length-1; i >= 0; i--){
            int num = nums2[i];
            while(!stack.isEmpty() && num >= stack.peek()){
                stack.pop();
            }
            map.put(num,stack.isEmpty()? -1 : stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            // nums1 是 nums2 的子集
            res[i] = map.get(nums1[i]);
        }
        return res;
    }

[MollyMozz]

倒着遍历的妙处在于不用每次拷贝对应需要匹配的剩余数组吗，我自己正着遍历写了一遍再看倒着写的这个思路感觉是这样。

[MollyMozz]

js版本

function findNextBigEle2(nums) {
    const res = [];
    const stack = [];
    for(let i = nums.length -1; i >= 0; i--) {
        while(stack.length !== 0 && stack[0] <= nums[i]) {
            stack.shift();
        }
        res.unshift(stack.length ? stack[0] : -1);
        stack.unshift(nums[i])
    }
    return res;
}

[ElandWoo]

503.下一个更大的元素 [CPP]

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        stack<int> s;
        vector<int> ans(n, -1);
        for (int i = 0; i < 2 * n - 1; ++i) {
            while (!s.empty() && nums[s.top()] < nums[i % n]) {
                ans[s.top()] = nums[i % n];
                s.pop();
            }
            s.push(i % n);
        }
        return ans;
    }
};

[jennyliulfm]

circular next greater element 用double the size，然后取余绝了 虽然计算了两遍，但是没有复杂逻辑 容易理解 记忆 总结规律。点赞点赞。用站队 很形象的描述了单调栈的本质 在写while loop 保持栈的单调递增或者单调递减的时候 再也不用犹豫 condition了

[bert82503]

打卡，感谢楼主！

[deepbreath373]

check in

[yonggui-yan]

打卡，点赞

[pxie2120]

1

[zdcat]

最后一题索引取余属实是太妙了，res会被刷新一遍，不过这种思路我自己肯定是想不到了哈哈哈

[bruceeewong]

打卡，单调栈是个很有意思的数据结构呀，可以在无序的数组里找到递增/减的子序列，厉害

[Hanmu-Zuo]

我现在发现难的不是算法本身，是如何把现实问题抽象成算法问题。这个太难了，题目的描述可以有千万种说法，很遗憾我还没能融会贯通把题目描述简化抽象成做过的算法，哎

[labuladong]

在生活中遇到问题时可以尝试多思考是否可以用算法解决，从而练习这种抽象能力。

[somepiga]

妙不可言