当前位置: 首页 > article >正文

刷代随有感(134):单调栈——下一个更大元素I(难点涉及哈希表与单调栈的结合)

单调栈处理的是下标!

题干:

代码:

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int>ddst;
        unordered_map<int,int>umap;
        vector<int>res(nums1.size(), -1);
        if(nums1.size() == 0)return res;

        for(int i = 0; i < nums1.size(); i++)
        {
            umap[nums1[i]] = i;
        }

        ddst.push(0);
        for(int i = 1; i < nums2.size(); i++)
        {
            if(nums2[i] <= nums2[ddst.top()]) ddst.push(i);
            else
            {
                while(!ddst.empty() && nums2[i] > nums2[ddst.top()])
                {
                    //结果记录
                    if(umap.count(nums2[ddst.top()]) > 0)
                    {
                        int index = umap[nums2[ddst.top()]];//获取此数组2元素(栈顶)在数组1中下标值
                        res[index] = nums2[i];//将遍历到的(不是栈顶)放入res中
                    }
                    ddst.pop();//记录完成后弹出(持续)
                }
                ddst.push(i);
            }
        }

        return res;
        
    }
};

哈希表的思想:在数组2里找元素而在数组1里面确定,涉及映射关系考虑哈希map。


http://www.kler.cn/a/371846.html

相关文章:

  • Oracle视频基础1.1.3练习
  • 省域经济高质量发展水平测算及数据2000-2021年
  • C语言中的野指针以及避免野指针的常用方式
  • Linux——常见指令及其权限理解(正在更新中)
  • CNAS软件测试的好处有哪些?上海软件测试中心推荐
  • C#从零开始学习(用户界面)(unity Lab4)
  • jenkins搭建及流水线配置
  • 求助帖:ubuntu22.10 auto install user-data配置了为何还需要选择语言键盘(如何全自动)
  • python通过translate库实现中英文翻译
  • 【libGL error】Autodl云服务器配置ACT的conda虚拟环境生成训练数据时,遇到了libGL相关错误,涉及swrast_dri.so
  • 数据采集(全量采集和增量采集)
  • 三方接口调用设计方案
  • 3. STM32之TIM实验--输出比较(PWM输出,电机,四轴飞行器,智能车,机器人)--(实验1:PWM驱动LED呼吸灯)
  • sparksql建临时表的几种方式
  • Java | Leetcode Java题解之第513题找树左下角的值
  • 数据结构 ——— 二叉树的概念及结构
  • 联动香港、成都、武汉三所高校!“2024 深圳国际金融科技大赛”校园行圆满结束
  • MySql基础34题写题记录(21-29)
  • 【AI】numpy_pandas_matplotlib_sklearn合集
  • macOS Sonoma 14.7.1 (23H222) Boot ISO 原版可引导镜像下载
  • 没有对象来和我手撕红黑树吧
  • 安装git-lfs发生报错Could not find Git; can not register Git LFS.解决方案
  • Milvus - 内存索引类型详解
  • 中阳金融智能量化交易系统的创新与未来发展
  • 出海要深潜,中国手机闯关全球化有了新标杆
  • 网络安全包含哪些方面?如何加强网络安全建设?