C++单调向量算法:132 模式解法三枚举1

简介: C++单调向量算法:132 模式解法三枚举1

本题不同解法

分析

时间复杂度

2轮循环时间复杂度都是O(n)。

步骤

第一步

枚举32,再将2to3,转成3to2。枚举2。v3ValueIndex|记录nums[0,k)所有的值的索引。然后在v3ValueIndex中寻找值大于iValue,如果有多个结果取索引最大的。如果value0 <= value1且index0 <= index1,则value0被index0淘汰。能选取vaule0则必定能选择vaule1,而index1比index0大。淘汰后,值按降序排序,3Index按升序排序。由于索引是越来越大,所以只会淘汰旧值,不会被旧值淘汰。由于淘汰值小的,所以可以从末尾淘汰。按索引升序插入,而索引是按升序排序的,所以插入也在末尾。故可以用栈或向量代替有序映射。在尾部增加、删除时间复杂度都是O(1)。

第二步

枚举1。如果m3IndexTo2Value(i,m_c)中存在比nums[i]大的值,则存在132模式,否则不存在。注意:m3IndexTo2Value 有些key会不存在。std::unordered_map不存在的值是0,而本题的值可能是负数。

关于2to3转成3to2

计算2to3的过程中,会淘汰一些组合,不影响结果。2to3转成3to2的时候,也会淘汰一些组合,被淘汰的不影响最终结果。m3IndexTo2Value, 3Index相同,淘汰值小的。如果值小的都大于nums[i],那么值的一定大于nums[i]。我们只要确保没被淘汰的组合都被枚举到,旧可以了。

代码

核心代码

class Solution {
public:
  bool find132pattern(vector<int>& nums) {
    m_c = nums.size();
    const int iNotMayMinValue = -1000 * 1000 * 1000 - 1;
    {
      vector < std::pair<int, int>> v3ValueIndex;//3Value的值按降序排序,3Index按升序排序
      for (int k =0 ; k < m_c ; k++ )
      {
        const int& iValue = nums[k];
        while (v3ValueIndex.size() && (v3ValueIndex.back().first <= iValue))
        {
          v3ValueIndex.pop_back();
        }
        if (v3ValueIndex.size())
        {
          const int i3Index = v3ValueIndex.back().second;
          if (!m3IndexTo2Value.count(i3Index) || (m3IndexTo2Value[i3Index] < iValue))
          {
            m3IndexTo2Value[i3Index] = iValue;
          }
        }
        v3ValueIndex.emplace_back(iValue, k);
      }
    }
    //寻找1,即nums[i]
    {
      int iMaxTow = iNotMayMinValue;
      for (int i = m_c - 1; i >= 0; i--)
      {
        const int& iValue = nums[i];
        if( iMaxTow > iValue )
        {
          m_iIndex1 = i;
          return true;
        }
        if (m3IndexTo2Value.count(i))
        {
          iMaxTow = max(iMaxTow, m3IndexTo2Value[i]);
        }
      }
    }
    return false;
  }
  std::unordered_map<int, int> m3IndexTo2Value;
  int m_iIndex1 = -1;
  int m_c;
};

测试代码

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
vector nums;
bool res;
{
Solution slu;
nums = { 3,5,0,3,4 };
res = slu.find132pattern(nums);
//Assert(vector{5, 0, 5, 2, 0}, slu.m_v3To1);
Assert(0, slu.m_iIndex1);
Assert(true, res);
}
{
nums = { 1 ,2, 3,4 };
res = Solution().find132pattern(nums);
Assert(false, res);
}
{
Solution slu;
nums = { 3,1,4,2 };
res = slu.find132pattern(nums);
//Assert(vector{4, 4, 0, 1}, slu.m_v3To1);
Assert(1, slu.m_iIndex1);
Assert(true, res);
}
{
Solution slu;
nums = { -1,3,2,0 };
res = slu.find132pattern(nums);
//Assert(vector{4, 0, 0, 0}, slu.m_v3To1);
Assert(0, slu.m_iIndex1);
Assert(true, res);
}
{
Solution slu;
nums = { 1, 0, 1, -4, -3 };
res = slu.find132pattern(nums);
//Assert(vector{4, 0, 0, 0}, slu.m_v3To1);
Assert(-1, slu.m_iIndex1);
Assert(false, res);
}
//CConsole::Out(res);

}

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

洒家想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
墨家名称的来源:有所得以墨记之。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17

或者 操作系统:win10 开发环境: VS2022 C++17


相关文章
|
4月前
|
C++ 容器
C++中向量的操作vector
C++中向量的操作vector
|
14天前
|
前端开发 算法 JavaScript
无界SaaS模式深度解析:算力算法、链接力、数据确权制度
私域电商的无界SaaS模式涉及后端开发、前端开发、数据库设计、API接口、区块链技术、支付和身份验证系统等多个技术领域。本文通过简化框架和示例代码,指导如何将核心功能转化为技术实现,涵盖用户管理、企业店铺管理、数据流量管理等关键环节。
|
2月前
|
存储 算法 安全
超级好用的C++实用库之sha256算法
超级好用的C++实用库之sha256算法
66 1
|
18天前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
14 0
|
27天前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)
|
27天前
|
人工智能 算法 Java
【搜索算法】数字游戏(C/C++)
【搜索算法】数字游戏(C/C++)
|
2月前
|
存储 算法 安全
超级好用的C++实用库之国密sm4算法
超级好用的C++实用库之国密sm4算法
43 0
|
2月前
|
算法 安全 Serverless
超级好用的C++实用库之国密sm3算法
超级好用的C++实用库之国密sm3算法
36 0
|
2月前
|
算法 数据安全/隐私保护 C++
超级好用的C++实用库之MD5信息摘要算法
超级好用的C++实用库之MD5信息摘要算法
56 0
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
49 6