fucking-algorithm 单调栈结构解决三道算法题

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

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

Aug 11 '21 12:08 utterances-bot

000

Aug 11 '21 12:08 taoweidong

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

Jan 26 '22 08:01 fornobugworld

倒着写不是多此一举吗？

Apr 16 '22 23:04 CNS1mple

第一题文章里只给了一个模板，没有给出对应原题的题解，如果不仔细看原题，只看文章的话，可能会感觉比较困惑，建议做的时候细品原题题干～给一个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
};

Apr 20 '22 16:04 5Reeson

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;
    }

Apr 24 '22 09:04 lzh2580

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

May 16 '22 14:05 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;
}

May 16 '22 14:05 MollyMozz

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;
    }
};