数据结构与算法笔记：字典序最大问题分析

2024-07-17 20:08| 来源: 网络整理| 查看: 265

字典序最大问题

问题描述

给定一个1到n的排列(无序状态的)，依次插入到栈中，在每时每刻都可以多次从栈中弹出栈顶问：应如何使得弹出栈顶的序列的字典序最大，并输出这个序列

问题分析

什么是字典序比如两个序列：5,4,3,2,1和1,2,3,4,5这两个中第一个的字典序最大每个位置上的数字比其他序列上同一位置的数字要大比如：第一位置中5比1大，第二位置中4比2大这样即：字典序最大 = 从左向右看这个序列，每个数字都尽量大题目给定一个1到n的排列，每个数字只出现一次要使出栈的字典序最大，则第一个出栈的一定是n, 也就是序列中的最大值，同时n的入栈和出栈动作一定是连续的，不会被其他元素所干扰第二个出栈的会是谁呢？在n出栈之前，n前面的所有元素都一定在栈中，没有一个被弹出去，否则第一个弹出的位置就不会是n由于每次只能弹出栈顶，我们只需考虑栈顶的数字和n这个数字后面的元素中选一个最大值作为第二个出栈的候选者第三、第四等等以此类推总结一下，这个算法实现需要三个功能栈的基本操作连续一段(至末尾)序列最大值的查找判断谁是下一个出栈：当前栈顶与前一个出栈元素后面的元素中最大的那个关键算法实现

1 ）蛮力算法：算法复杂度为： O ( n 2 ) O(n^2) O(n2)

每次花费O(n)的时间查找最大值一共进行了O(n)次算法复杂度为： O ( n 2 ) O(n^2) O(n2) // n: 序列长度 // ele：序列数组，下标从0开始 // 返回值：返回字典序最大的出栈序列 vector getResult(int n, int *ele) { vector ans; // 动态数组，用于返回 stack s; // 用于存放索引的栈 // 处理当前所有的元素 for (int i = 0; i mx = max(mx, ele[j]); } // 如果栈不空且栈顶元素较大，则将较大的栈顶弹出(满足字典序最大) if(!s.empty() && ele[s.top()] > mx) { ans.push_back(ele[s.top()]); // 将这个较大栈顶存入结果 s.pop(); // 出栈 } else { // 将最大值之外的元素全部压进去(因为最大值只有一个，所以用!=的方式处理除了最大值之外的所有元素) while(mx!=ele[i]) { s.push(i); // 入栈 ++i; // i自增跳出while，重新执行外层循环 } // 当前的i元素ele[i]就是最大值的时候，将这个最大值存入结果 ans.push_back(ele[i]); ++i; } } // 当外面的元素全都没有了(该入栈的都入栈了)，最后只能从栈中一个一个弹出来了，将剩余元素依次弹出，并存入最终结果 while(!s.empty()) { ans.push_back(ele[s.top()]); s.pop(); } return ans; }

2 ）线性算法：算法复杂度为： O ( n ) O(n) O(n)

维护一个数组maxElement,表示位置i到位置n的最大值 m a x E l e m e n t i = m a x { m a x E l e m e n t i + 1 , e l e m e n t i } maxElement_i = max\{ maxElement_{i+1}, element_i \} maxElementi=max{maxElementi+1,elementi}算法开始之前做数据的预处理，时间复杂度为O(n) 之后，算法查询O(n)次，每次花费O(1)的时间来查询最大值，结合之前预处理时间也是O(n), 所以总时间复杂度还是O(n)以空间换时间，妥妥的线性算法, 非常高效 // n: 序列长度 // ele：序列数组，下标从0开始 // 返回值：返回字典序最大的出栈序列 vector getResult(int n, int *ele) { vector ans; // 动态数组，用于返回 stack s; // // ----- 数据预处理开始 ----- // int *maxElement = new int[n](); // 定义一个存储所有元素的空间 maxElement[n-1] = ele[n-1]; // 初始化最后一个元素，作为切入点 // 批量处理其他元素，注意，此处是倒序，最大值的比较是当前元素和前一个最大值(序号较大的，因为是倒序循环) for(int i=n-2; i>=0; --i) { maxElement[i] = max(maxElement[i+1], ele[i]); } // ----- 数据预处理结束 ----- // // 遍历当前所有的元素 O(n) for (int i = 0; i ans.push_back(ele[s.top()]); // 将这个较大栈顶存入结果 s.pop(); // 出栈 } else { // 将最大值之外的元素全部压进去(因为最大值只有一个，所以用!=的方式处理除了最大值之外的所有元素) while(mx!=ele[i]) { s.push(i); // 入栈 ++i; // i自增跳出while，重新执行外层循环 } // 当前的i元素ele[i]就是最大值的时候，将这个最大值存入结果 ans.push_back(ele[i]); ++i; } } // 当外面的元素全都没有了(该入栈的都入栈了)，最后只能从栈中一个一个弹出来了，将剩余元素依次弹出，并存入最终结果 while(!s.empty()) { ans.push_back(ele[s.top()]); s.pop(); } return ans; }

3 ) 其他复杂度算法： O ( n l o g n ) O(nlogn) O(nlogn)

既然解决方案可以从 O ( n 2 ) O ( n ) O(n^2) ~ O(n) O(n2) O(n), 那么O(nlogn)的复杂度也可以实现每一次查询只会花费O(logn)的时间，构建以及其他零散总时间也不会超过O(nlogn)可以参考：线段树，堆，平衡树来考虑，此处不再赘述具体替换的位置在下面，替换上上面的一些技术来做查询// 找到当前最大值(并非全局最大值，第一次循环的时候是全局最大值) for (int j = i; j int n; cin >> n; int *ele = new int[n](); // 输入的数组 // 初始化 for (int i = 0; i cout

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章