力扣题记之单调栈

More content:LeetCode hot100@栈

96. 下一个更大元素 I

单调栈 + 哈希

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> sk; // 单调栈存下标,保持对应元素值递减
        unordered_map<int, int> mp; 
        for(int i = 0; i < nums2.size(); i++) {
            while(!sk.empty() && nums2[i] > nums2[sk.top()]) {
                mp[nums2[sk.top()]] = nums2[i];
                sk.pop();
            }
            sk.push(i);
        }

        vector<int> res(nums1.size(), -1);
        for(int i = 0; i < nums1.size(); i++) {
            if(mp.find(nums1[i]) != mp.end()) {
                res[i] = mp[nums1[i]];
            }
        }

        return res;
    }
};

496. 下一个更大元素 I

在上一题的基础上 先扩充一倍 因为总能在两次遍历内找到 最后再将结果缩减一倍

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> sk; // 单调栈存下标,保持对应元素值递减
        vector<int> res(2 * nums.size(), -1);
        vector<int> v(nums);
        v.insert(v.end(), nums.begin(), nums.end()); // 拼接数组
        for(int i = 0; i < v.size(); i++) {
            while(!sk.empty() && v[i] > v[sk.top()]) {
                res[sk.top()] = v[i];
                sk.pop();
            }
            sk.push(i);
        }
        res.resize(nums.size());

        return res;
    }
};

402. 移掉 K 位数字

比较两个数字的大小,是从最高位开始比较的,因此尽量使最高位变小,也就是改造使得数字从高位到低位递增。

因此想到维护一个递增单调栈来保证最高位最小,当遇到小于栈顶的元素时,就把栈顶这个大数去掉。

class Solution {
public:
    string removeKdigits(string num, int k) {
        stack<int> sk; // 递增栈 存下标 以此来保证最高位最小
        for(int i = 0; i < num.size(); i++) {
            while(!sk.empty() && num[i] < num[sk.top()] && k > 0) {     
                sk.pop();
                k--;
            }
            sk.push(i);
        }
        
        while(!sk.empty() && k > 0) { // 如果 k 还有余量
            sk.pop();
            k--;
        }

        // cout << "---------------------" << endl;
        // stack<int> tmp = sk;
        // while(!tmp.empty()) {
        //     cout << tmp.top() << " ";
        //     tmp.pop();
        // }
        // cout << endl << "---------------------" << endl;

        if(sk.empty()) return "0";
        string res;
        while(!sk.empty()) {
            res += num[sk.top()];
            sk.pop();
        }
        reverse(res.begin(), res.end());
        // 处理前导零
        int p = 0;
        int i = 0;
        for(i = 0; i < res.size(); i++) {
            if(res[i] == '0') p++;
            else break;
        }
        if(i == res.size()) return "0"; // 只有零的情况
        return res.substr(i); // 只填第一个参数
    }
};

42. 接雨水

Solution1:双指针 (按列计算)

每一列雨水的高度取决于,该列左侧最高的柱子和右侧最高的柱子中较矮的那个柱子的高度 – 自身高度

Solution2:单调栈 (按行计算)

栈底到栈头元素递减,因为一旦要添加的柱子高度大于栈头元素,说明出现凹槽了

此时,栈头元素就是凹槽底部的柱子,栈头第二个元素就是凹槽左边的柱子,而添加的元素就是凹槽右边的柱子

class Solution1 {
public:
    int trap(vector<int>& height) {
        int res = 0;
        int len = height.size();
        //记录当前列的左右两边的最高列
        vector<int> lmax(len);
        vector<int> rmax(len);
        
        lmax[0] = height[0];
        for(int i = 1; i < len; i++) {
            lmax[i] = max(lmax[i-1], height[i]);
        }

        rmax[len - 1] = height[len - 1];
        for(int i = len - 2; i >= 0; i--) {
            rmax[i] = max(rmax[i+1], height[i]);
        }

        for(int i = 0; i < height.size(); i++) {
            int x = min(lmax[i], rmax[i]) - height[i]; //第一列和最后一列的x算出来是0           
            if(x > 0) res += x; //是正数才说明能接住雨水,负数的情况比如最高列
        }

        return res;
    }
};
class Solution2 {
public:
    int trap(vector<int>& height) {
        stack<int> sk; //存下标
        int res = 0;
        sk.push(0);

        for(int i = 1; i < height.size(); i++) {
            while(!sk.empty() && height[i] > height[sk.top()]) { //出现凹槽
                int mid = height[sk.top()]; //凹槽中间柱子高度
                sk.pop();
                if(!sk.empty()) {
                    int left = height[sk.top()]; //凹槽左边柱子高度
                    int right = height[i]; //凹槽右边柱子高度
                    int h = min(left, right) - mid;
                    int w = i - sk.top() - 1;
                    res += h * w; //高×宽
                }
            }
            sk.push(i);
        }

        return res;
    }
};


不准投币喔 👆

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇